[BZOJ3782]上学路线 - A-Failure的博客

题目

Description

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

Input

第一行，四个整数N、M、T、P。

接下来的T行，每行两个整数，表示施工的路口的坐标。

Output

一行，一个整数，路径数mod P的值。

Sample Input

3 4 3 1019663265
3 0
1 1
2 2

Sample Output

HINT

1<=N,M<=10^10

0<=T<=200

p=1000003或p=1019663265

题解

如果没有不能走的位置，路径条数就是$C_{n+m}^{n}$

设$f_i$表示前$i-1$个障碍不走，走到第$i$个障碍的路径条数，那么有转移：

$f_i=C_{x_i+y_i}^{x_i}-\sum_{j=1}^{i-1}f_j\times C_{(x_i-x_j)+(y_i-y_j)}^{x_i-x_j},x_j\le x_i,y_j\le y_i$

表示全部的路径条数减去不合法的路径条数

发现模数有两个，一个挺小并且是质数，所以组合数直接用$Lucas$解决就行了

另一个不是质数，但是能分解成$3,5,6793,10007$，所以用$Lucas$搞出来$4$个质数的解再用$crt$合并就行了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e6+5,N=2e4+5;
struct p{
	LL x,y;
	bool operator< (const p &a)
	const{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
}A[N];
LL n,m;
int T,P;
int _P[4]={3,5,6793,10007};
int Pow(int a,int b,int mod)
{
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
	  if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
int Csmall(int a,int b,int mod,int *fac)
{
	if(a>b) return 0;
	return 1ll*fac[b]*Pow(fac[a],mod-2,mod)%mod*Pow(fac[b-a],mod-2,mod)%mod;
}
int C(LL a,LL b,int mod,int *fac)
{
	if(a>b) return 0;
	if(!b) return 1;
	return 1ll*C(a/mod,b/mod,mod,fac)%mod*Csmall(a%mod,b%mod,mod,fac)%mod;
}
int exgcd(int a,int b,int &x,int &y)
{
	if(!b) return x=1,y=0,a;
	int ans=exgcd(b,a%b,x,y),tt=x;
	return x=y,y=tt-a/b*y,ans;
}
struct Sub_1{
	int fac[MAX],f[N];
	void Solve()
	{
		fac[0]=fac[1]=1;
		for(int i=2;i<=P;++i)
		  fac[i]=1ll*fac[i-1]*i%P;
		for(int i=1;i<=T;++i)
		  {
		  	f[i]=C(A[i].x,A[i].x+A[i].y,P,fac);
		  	for(int j=1;j<i;++j)
		      if(A[i].x>=A[j].x&&A[i].y>=A[j].y) f[i]=(f[i]-1ll*f[j]*C(A[i].x-A[j].x,A[i].x-A[j].x+A[i].y-A[j].y,P,fac)%P+P)%P;
		  }
		printf("%d",f[T]);
	}
}OAO;
struct Sub_2{
	int f[N];
	int fac[4][N],inv[4][N],B[4];
	int _C(LL a,LL b)
	{
		int ans=0;
		for(int i=0,M,x,y;i<4;++i)
		  M=P/_P[i],exgcd(M,_P[i],x,y),ans=(ans+1ll*M*((x%_P[i]+_P[i])%_P[i])%P*C(a,b,_P[i],fac[i])%P)%P;
		return ans;
	}
	void Solve()
	{
		for(int j=0;j<4;++j)
		  {
		  	fac[j][0]=fac[j][1]=inv[j][1]=1;
		  	for(int i=2;i<=_P[j];++i)
			  fac[j][i]=1ll*fac[j][i-1]*i%_P[j],inv[j][i]=(-_P[j]/i*inv[j][_P[j]%i]%_P[j]+_P[j])%_P[j];
		  }
		for(int i=1;i<=T;++i)
		  {
		  	f[i]=_C(A[i].x,A[i].x+A[i].y);
		  	for(int j=1;j<i;++j)
		      if(A[i].x>=A[j].x&&A[i].y>=A[j].y) f[i]=(f[i]-1ll*f[j]*_C(A[i].x-A[j].x,A[i].x-A[j].x+A[i].y-A[j].y)%P+P)%P;
		  }
		printf("%d",f[T]);
	}
}OUO;
int main()
{
	scanf("%lld%lld%d%d",&n,&m,&T,&P);
	for(int i=1;i<=T;++i)
	  scanf("%d%d",&A[i].x,&A[i].y);
	A[++T]=(p){n,m},sort(A+1,A+1+T);
	if(P==1e6+3) return OAO.Solve(),0;
	return OUO.Solve(),0;
}

题目