BZOJ 3782: 上学路 Lucas+ExCRT+容斥+dp

其实呢，扩展中国剩余定理还有一种理解方式：就是你有一坨东西，形如：
$A[i]\equiv B[i](mod$ $P[i])$.
对于这个东西，你可以这么思考：
如果最后能求出一个解，那么这个解的增量一定是 $lcm(P[1],P[2].....).$
所以，只要你能找到一坨 $P[i]$，使得它们的 $lcm$ 等于你想要的东西，你就可以用 $excrt$来解.

p话扯完了，我们步入正题：
假设没有障碍，有 $n$ 行 $m$ 列，那么答案即为 $C_{n+m}^{n}.$
这个东西就代表你一共会走 $n+m$ 步，其中 $n$ 步的方向是向上的.
而如果有障碍，我们考虑按照每一个障碍点一次枚举.
首先，将障碍按照横纵坐标从小到大拍一个序，那么考虑我们枚举到第 $i$ 个障碍.
令 $f[i]$ 表示从起点到第 $i$ 个障碍所走过的合法的方案数，$(x,y)$ 表示横纵坐标.
总方案为 $C_{x+y}^{y},$ 不合法的方案为 $\sum f[前面障碍]$.
如果随便减的话，我们可能减多，所以我们考虑按照策略去减.
我们想让每一次减掉的都互不相同，所以我们考虑枚举第一个不合法的障碍.
即 $C_{x+y}^{y}-\sum_{j=1}^{i-1}f[j]\times calc(j到i的方案数).$
这样，我们等于说是强制性的每次只减掉第一个障碍碰到 $j$ 的方案数，不会减多.
这个题的模数不是素数，所以需要将模数分解成若干个素数，然后依次取模，最后在用 $excrt$ 合并.

Code:

#include <cstdio>

#include <algorithm>

#define N 1000006

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

ll F[N];

int array[10]={0,3,5,6793,10007};

struct Node {

	ll x,y;

	Node(ll x=0,ll y=0):x(x),y(y){}

}arr[N];

bool cmp(Node a,Node b) {

	return a.x==b.x?a.y<b.y:a.x<b.x;

}

ll qpow(ll base,ll k,ll mod) {

	ll tmp=1;

	for(;k;k>>=1,base=base*base%mod)

		if(k&1) tmp=tmp*base%mod;

	return tmp;

}

struct Lucas {

	int mod;

	int fac[N];

	int inv(int i) {

		return (int)qpow(i,mod-2,mod);

	}

	void init(int p) {

		mod=p,fac[0]=1;

		for(int i=1;i<=mod;++i) fac[i]=(ll)fac[i-1]*i%mod;

	}

    int C(int x,int y) {

    	if(y>x) return 0;

    	if(y==0) return 1;

    	return (int)(1ll*fac[x]*inv(fac[y])%mod*inv(fac[x-y])%mod);

    }

    int solve(ll x,ll y) {

    	if(y>x) return 0;

    	if(y==0) return 1;

    	return (int)(1ll*solve(x/mod,y/mod)*C(x%mod,y%mod)%mod);

    }

}comb[8];

struct excrt {

	ll arr[N],brr[N];

	ll exgcd(ll a,ll b,ll &x,ll &y) {

		if(!b) {

			x=1,y=0;

			return a;

		}

		ll gcd=exgcd(b,a%b,x,y),tmp=x;

		x=y,y=tmp-a/b*y;

		return gcd;

	}

	ll Excrt() {

		int i,j;

		ll ans=arr[1],M=brr[1];

        for(i=2;i<=4;++i) {

        	ll a=M,b=brr[i],c=arr[i]-ans,gcd,x,y;

        	gcd=exgcd(a,b,x,y),b=abs(b/gcd);

        	x=(x*(c/gcd)%b+b)%b;

        	ans+=M*x;

        	M*=brr[i]/__gcd(brr[i],M);

        	ans=(ans%M+M)%M;

        }

        return ans;

	}

}crt;

ll C(ll a,ll b,int ty) {

	if(ty==0)

		return comb[0].solve(a,b);

	else {

		int i,j;

		for(i=1;i<=4;++i) {

			crt.arr[i]=comb[i].solve(a,b);

			crt.brr[i]=array[i];

		}

	}

	return crt.Excrt();

}

int main() {

	int i,j,k,flag;

	// setIO("input");

	ll n,m,mod;

	scanf("%lld%lld%d%lld",&n,&m,&k,&mod),flag=(mod==1019663265);

	if(!flag) {

		comb[0].init(mod);

	}

	else {

		for(i=1;i<=4;++i)

			comb[i].init(array[i]);

	}

	for(i=1;i<=k;++i)

		scanf("%lld%lld",&arr[i].x,&arr[i].y);

	arr[++k].x=n,arr[k].y=m;

	sort(arr+1,arr+1+k,cmp);

	for(i=1;i<=k;++i) {

		F[i]=C(arr[i].x+arr[i].y,arr[i].y,flag);

		for(j=1;j<i;++j) {

			if(arr[j].y<=arr[i].y)

				F[i]=(F[i]-(F[j]*C(arr[i].x-arr[j].x+arr[i].y-arr[j].y,arr[i].y-arr[j].y,flag)%mod)+mod)%mod;

		}

	}

	printf("%lld\n",F[k]);

	return 0;

}

巴特西

BZOJ 3782: 上学路 Lucas+ExCRT+容斥+dp

最新文章

热门文章