这份代码,n,m为int的时候,第六个测试点测出来会RE,因为cin的时候,n,m应该超过int_max了,导致mod=0。 但题目保证n,m不超过1e9
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define inf 0x3f3f3f3f3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=1e6+500;
ll N,M,MOD;
int T;
struct Lucas{
ll ff[maxn+5],mod;
void init(){
ff[0]=1;
FOR(i,1,maxn)ff[i]=(ff[i-1]*i)%mod;//处理P大小
}
ll gcd(ll a,ll b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
ll x,y;
void Extended_gcd(ll a,ll b)
{
if(b==0)
{
x=1;
y=0;
}
else
{
Extended_gcd(b,a%b);
ll t=x;
x=y;
y=t-(a/b)*y;
}
}
//计算不大的C(n,m)
ll C(ll a,ll b)
{
if(b>a)return 0;
b=(ff[a-b]*ff[b])%mod;
a=ff[a];
ll c=gcd(a,b);
a/=c;b/=c;
Extended_gcd(b,mod);
x=(x+mod)%mod;
x=(x*a)%mod;
return x;
}
//Lucas定理
ll Combination(ll n, ll m)
{
ll ans=1;
ll a,b;
while(m||n)
{
a=n%mod;
b=m%mod;
n/=mod;
m/=mod;
ans=(ans*C(a,b))%mod;
}
return ans;
}
}ls[5];
ll a[2000],m[2000],Mi[2000];//a是余数,m是模数
bool ok=false;
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){x=1,y=0;return ;}
exgcd(b,a%b,x,y);
ll z=x;x=y,y=z-y*(a/b);
}
//对于给定的x,对mi取模,再反解最小x,对P取模即对非质数取模方法。
void get_a(ll x,ll y){
for(int i=1;i<=4;i++)a[i]=ls[i].Combination(x,y);
}
ll crt(int n){
ll mul=1,ret=0;
for(int i=1;i<=n;i++)mul*=m[i];
for(int i=1;i<=n;i++){
Mi[i]=mul/m[i];
ll x=0,y=0;
exgcd(Mi[i],m[i],x,y);
ret+=a[i]*Mi[i]*(x<0?x+m[i]:x);
}
return ret%mul;
}
ll get(ll x,ll y){
if(ok){
return ls[0].Combination(x,y)%MOD;
}
else{
get_a(x,y);
return crt(4)%MOD;
}
}
ll dp[maxn];
struct node{ll x,y;}A[maxn];
int main(){
cin>>N>>M>>T>>MOD;
// scanf("%d%d%d%lld",&N,&M,&T,&MOD);
ls[0].mod=1000003,m[1]=ls[1].mod=3,m[2]=ls[2].mod=5,m[3]=ls[3].mod=6793,m[4]=ls[4].mod=10007;
for(int i=0;i<=4;i++)ls[i].init();
if(MOD==1000003)ok=true;
for(int i=1;i<=T;i++)scanf("%d%d",&A[i].x,&A[i].y);
T++,A[T].x=N,A[T].y=M;
sort(A+1,A+1+T,[](node a,node b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
});
for(int i=1;i<=T;i++){
ll ret=get(A[i].x+A[i].y,A[i].x);
for(int j=1;j<i;j++){
if(A[i].x>=A[j].x&&A[i].y>=A[j].y)ret=((ret-dp[j]*get(A[i].x-A[j].x+A[i].y-A[j].y,A[i].x-A[j].x))%MOD+MOD)%MOD;
}
dp[i]=ret%MOD;
}
cout<<dp[T];
}