P4478 [BJWC2018]上学路线

n 和 m 都很大，所以可以从 T 的角度考虑，根据障碍点进行 dp。

然后设 f[i]表示表示第一次经过 i 且 i 为第一个障碍时的方案数。

然后考虑容斥，有：
\[f[i]=C_{p[i].x+p[i].y}^{p[i].x}-\sum_{j}[p[j].x<=p[i].x\& \& p[j].y<=p[i].y]f[j]\times C_{p[i].x-p[j].x+p[i].y-p[j].y}^{p[i].x-p[j].x}\]

然后排序一下，

然后由于 n，m 很大，所以可以用 Lucas 定理求组合数，然后由于模数可能不是质数，所以还要用 CRT 合并。

复杂度：\(O(T^2\log_{mod}N)\)。

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=207;
const int M=1000007;
template <class I>
inline void read(I &x){
    int f=1;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c&15),c=getchar());
    x*=f;
}
ll n,m,T,P,jc[M],invjc[M],f[N],ans;
struct node{
    ll x,y;
    inline bool operator < (const node &a) const{
        return x==a.x?y<a.y:x<a.x;
    }
    inline void rd(){
        read(x),read(y);
    }
}p[N];
ll ksm(ll x,ll y,ll mod){
    ll res=1;
    while(y){
        if(y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0) {x=1,y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll z=x;x=y,y=z-(a/b)*y;
    return d;
}
ll C(ll x,ll y,ll mod){
    if(y>x) return 0;
    if(x<mod&&y<mod) return 1ll*jc[x]*invjc[y]%mod*invjc[x-y]%mod;
    return 1ll*C(x%mod,y%mod,mod)*C(x/mod,y/mod,mod)%mod;
}
ll solve(ll mod){
    jc[0]=jc[1]=1;
    for(ll i=2;i<mod;i++)
        jc[i]=1ll*jc[i-1]*i%mod;
    invjc[mod-1]=ksm(jc[mod-1],mod-2,mod);
    for(ll i=mod-2;i>=0;i--)
        invjc[i]=1ll*invjc[i+1]*(i+1)%mod;
    for(ll i=1;i<=T+1;i++){
        f[i]=C(p[i].x+p[i].y,p[i].x,mod);
        for(ll j=1;j<i;j++)
            if(p[j].x<=p[i].x&&p[j].y<=p[j].y)
                f[i]=(((ll)f[i]-1ll*f[j]*C(p[i].x+p[i].y-p[j].x-p[j].y,p[i].x-p[j].x,mod))%mod+mod)%mod;
    }
    return f[T+1];
}
ll bing(ll a,ll b,ll c){
    ll x=0,y=0;
    exgcd(a,c,x,y);
    x=(x%c+c)%c;
    return 1ll*x*a%P*b%P;
}
int main(){
    read(n),read(m),read(T),read(P);
    for(ll i=1;i<=T;i++)
        p[i].rd();
    p[T+1].x=n,p[T+1].y=m;
    sort(p+1,p+2+T);
    if(P==1000003) {
        printf("%lld\n",solve(1000003));
        return 0;
    }
    ll ans1=solve(3),ans2=solve(5),ans3=solve(6793),ans4=solve(10007);
    ans=(ans+bing(P/3,ans1,3))%P;
    ans=(ans+bing(P/5,ans2,5))%P;
    ans=(ans+bing(P/6793,ans3,6793))%P;
    ans=(ans+bing(P/10007,ans4,10007))%P;
    cout<<ans<<endl;
    return 0;
}