[BJWC2018]上学路线

Description

小B 所在的城市的道路构成了一个方形网格，它的西南角为(0,0)，东北角为(N,M)。

小B 家住在西南角，学校在东北角。现在有T 个路口进行施工，小B 不能通过这些路口。小B 喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小B又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小B 只需要让你求出路径数mod P 的值。

---

\((0,0)\to (N,M)\)的路径数是\(C_{n+m}^n\)

\(f[i]\)表示第一个到达的障碍是\(i\)时\((0,0)\to (x_i,y_i)\)的路径数

\[（）f[i]=C_{x_i+y_i}^{x_i}-\sum C_{x_i+y+_i-x_j-y_j}^{x_i-x_j}\times f[j]（x_j\leq x_i\wedge y_j\leq y_i）
\]

\(1019663265\)一看就不是质数啊$=3\times 5\times 6793\times 10007 $

用中国剩余定理合并

---

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define M 1000010

using namespace std;

LL n,m,t,p,A[M],B[M],inv[M],f[201],ans1,ans2,ans3,ans4;

struct vv { LL x,y;} a[201];

bool cmp(vv a,vv b){return (a.x!=b.x? a.x<b.x : a.y<b.y);}

LL C(LL x,LL y,LL p)

{

	if(y>x) return 0;

	if(x<p && y<p) return A[x]*B[y]%p*B[x-y]%p;

	return C(x/p,y/p,p)*C(x%p,y%p,p)%p;

}

LL solve(LL p)

{

	LL ans=0;

	A[0]=B[0]=inv[1]=1;

	for(int i=2;i<p;i++) inv[i]=(p-p/i)*inv[p%i]%p;

	for(int i=1;i<p;i++) A[i]=A[i-1]*i%p;

	for(int i=1;i<p;i++) B[i]=B[i-1]*inv[i]%p;

	for(int i=1;i<=t;i++)

	{

		f[i]=C(a[i].x+a[i].y,a[i].x,p);

		for(int j=1;j<i;j++) if(a[j].x<=a[i].x && a[j].y<=a[i].y)

			f[i]=(f[i]-f[j]*C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].y-a[j].y,p)%p+p)%p;

	}

	ans=C(n+m,m,p);

	for(int i=1;i<=t;i++) ans=(ans-f[i]*C(n+m-a[i].x-a[i].y,n-a[i].x,p)%p+p)%p;

	return ans;

}

LL ksm(LL x,LL y,LL p)

{

	LL z=1;

	for(;y>1;y>>=1, x=x*x%p) if(y&1) z=z*x%p;

	return x*z%p;

}

int main()

{

	scanf("%lld%lld%lld%lld",&n,&m,&t,&p);

	for(int i=1;i<=t;i++) scanf("%lld%lld",&a[i].x,&a[i].y);

	sort(a+1,a+1+t,cmp);

	if(p==1000003){ printf("%lld",solve(p)); return 0;}

	ans1=solve(3)*(p/3)%p*((p/3)%3)%p;  ans4=solve(10007)*(p/10007)%p*ksm(p/10007,10005,10007)%p;

	ans2=solve(5)*(p/5)%p*ksm(p/5,3,5)%p; ans3=solve(6793)*(p/6793)%p*ksm(p/6793,6791,6793)%p;

	printf("%lld",((ans1+ans2)%p+(ans3+ans4)%p)%p);

}