【LOJ#6374】网格（二项式反演，容斥）

时间：2023-03-09 09:36:18
【LOJ#6374】网格（二项式反演，容斥）

【LOJ#6374】网格（二项式反演，容斥）

题面

LOJ

要从\((0,0)\)走到\((T_x,T_y)\)，每次走的都是一个向量\((x,y)\)，要求\(0\le x\le M_x,0\le y\le M_y\)，并且不能不走。同时有\(k\)个限制，表示不能同时\(x=y=k_i\)，保证所有\(k_i\)都是\(G\)的倍数。求恰好跳了\(R\)步到达的方案数。

题解

如果不存在不能走的点的限制，那么两维可以分开考虑。比如接下来只考虑\(x\)上的问题。

因为存在步长的限制，所以设\(g(i)\)表示至少有\(i\)步超过了步长限制的方案数。

那么可以得到：

\[g(i)={R\choose i}{T_x-i*(M_x+1)+R-1\choose R-1}
\]

即将超过限制的步数直接走\(M_x+1\)步，那么剩下随意分配即可。

那么答案就可以容斥得到

\[Ans=\sum_{i=0}^R (-1)^ig(i)
\]

这个样子如果是在数轴上走显然是正确的，然而在本题中，要求了两维不能同时不走。意味着这个算出来的\(Ans_x*Ans_y\)实际上是至多走了\(R\)步的答案。

那么令\(g(i)\)表示至多走\(i\)步的答案，\(f(i)\)表示恰好走了\(i\)步的答案。

那么就可以得到：$$g(R)=Ans_x*Ans_y=\sum_{i=0}^R{R\choose i}f(i)$$

二项式反演之后得到：

\[f(R)=\sum_{i=0}^R(-1)^{R-i}{R\choose i}g(i)
\]

这样子就解决了没有额外限制的情况，时间复杂度为\(O(R^2)\)。

考虑存在额外限制的情况，设\(g(i)\)表示至少违反了\(i\)条规则的方案数，\(f(i)\)表示恰好。

那么有$$f(0)=\sum_{i=0}R(-1)ig(i)$$

考虑如何计算\(g(i)\)，那么记录\(S(x,s)\)表示一共违反了\(x\)条规则，并且他们的步数和为\(s\)的方案数，显然\(s=kG\)，所以只需要记录除\(G\)后的结果。而除\(G\)后最多不会超过\(100\)。对于每个\(S(x,s)\)，显然一共走了\(s*G\)步，所以剩下的随意走就可以用来更新\(g\)。

也就是$$g(i)=\sum_{j}S(i,j)Calc(T_x-jG,T_y-jG,M_x,M_y,R-i){R\choose i}$$

最后直接计算\(f(0)\)即可。

时间复杂度\(O(???)\)，分析不清了，然而跑得飞快。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MOD 1000000007

#define MAX 1100100

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int ans;

int Tx,Ty,Mx,My,R,G,N,NN,K,lim[55];

int jc[MAX],inv[MAX],jv[MAX];

int C(int n,int m){if(n<m||n<0||m<0)return 0;return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}

int Calc(int T,int M,int R)

{

	int ret=0;

	for(int i=0,d=1;i<=R;++i,d=MOD-d)

		if(T+R-1-i*(M+1)>=R-1)

			add(ret,1ll*d*C(R,i)%MOD*C(T+R-1-i*(M+1),R-1)%MOD);

		else break;

	return ret;

}

int Calc(int Tx,int Ty,int Mx,int My,int R)

{

	int ans=0;

	for(int i=0,d=(R&1)?MOD-1:1;i<=R;++i,d=MOD-d)

		add(ans,1ll*d*C(R,i)%MOD*Calc(Tx,Mx,i)%MOD*Calc(Ty,My,i)%MOD);

	return ans;

}

int S[120][120],g[120];

int main()

{

	Tx=read(),Ty=read();Mx=read();My=read();R=read();G=read();

	K=read();N=max(Tx,Ty)+R;NN=min(Tx,Ty)/G;

	for(int i=1;i<=K;++i)lim[i]=read()/G;

	sort(&lim[1],&lim[K+1]);K=unique(&lim[1],&lim[K+1])-lim-1;

	jc[0]=jv[0]=inv[0]=inv[1]=1;

	for(int i=1;i<=N;++i)jc[i]=1ll*jc[i-1]*i%MOD;

	for(int i=2;i<=N;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=N;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;

	S[0][0]=1;

	for(int i=1;i<=R&&i<=NN;++i)

		for(int k=1;k<=K;++k)

			for(int j=0;j+lim[k]<=NN;++j)

				add(S[i][j+lim[k]],S[i-1][j]);

	for(int i=0;i<=R&&i<=NN;++i)

		for(int j=0;j<=NN;++j)

			if(S[i][j])add(g[i],1ll*S[i][j]*Calc(Tx-j*G,Ty-j*G,Mx,My,R-i)%MOD*C(R,i)%MOD);

	for(int i=0,d=1;i<=R&&i<=NN;++i,d=MOD-d)add(ans,1ll*d*g[i]%MOD);

	printf("%d\n",ans);

	return 0;

}

相关文章