luogu 3158 [CQOI2011]放棋子

时隔多日我又来挑战这道dp。

几个月前给写自闭了。几个月后再来。

首先一个我们能列出来的状态是以行为转移的 f[i]表示前i行...但是会发现此时列我们控制不了且棋子的颜色,个数我们也要放到状态里。

这个dp是一个完成不了或者说复杂度过高的dp。

必须得换一个状态可以想到由于每种颜色棋子独立所以我们没有必要若干个颜色的棋子进行混合求方案。

可以一种一种颜色的棋子放。

所以有状态 f[i][j][k]表示前i种颜色的棋子占领了j行K列的方案数。

这样行和列的状态有了我们只需要安排一下当前颜色怎么放。

当前颜色有a[i]个棋子。枚举一下这么多棋子能占 l行 r列。

发现我们很难去形成用a[i]个棋子完美占领l行r列。但是若a[i]<l||a[i]<r方案数显然为0.

设S=空余的位置数 C(S,a[i])我们先强行安排位置。再减掉不合法的方案。

不合法方案=没有占领够l行+没有占领够r行-前两者的交集。

这里的容斥里面是一个类似于代表元容斥的东西。显然没够l行说明最多<=l-1都是不合法的对列同样如此。

最后两者不合法的交集要加回来即可。

不过这样容斥是错误的原因是我们的不合法方案中可能有状态是重复的如l-1行不合法我们外面还要乘一个C(l,l-1)*l-1行的不合法。

仔细观察 l-1行的不合法并不代表l-1行全部被占所以外面再乘以l说明一些方案被重复计算了但是不这样做也不对不合法的方案需要枚举出哪一行没有被占。

所以我们考虑一个新的容斥这次我们不合法方案定义为精确的占了wl,wr行确保他们都被占了这样就不会出现上述情况了。

但是wl,wr需要枚举我们需要把所有不合法的都给减掉。这样是\(c\cdot n^3\cdot m^3\)发现这个东西显然可以预处理一下所以复杂度降低一个nm.

这样总复杂度为\(sum \cdot n^2\cdot m^2\) 可以通过。我终于战胜了这道题目。

有的晕了。。

需要注意的是开longlong (我以为一个地方不会爆然后爆了千万不要以为！

对于预处理我们只需要处理a[i]即可我没想好把1~mx都给处理了。

const int MAXN=31,maxn=2010;

int n,m,c,maxx,mx;

int a[MAXN],vis[maxn];

ll g[maxn][MAXN][MAXN];//表示i个棋子占了j行k列的方案数。

ll f[MAXN][MAXN][MAXN];//f[i][j][k]表示前i种颜色占了i行j列的方案数.

ll fac[maxn],inv[maxn],ans;

inline int ksm(ll b,int p)

{

	ll cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b%mod;

		b=b*b%mod;

		p=p>>1;

	}

	return cnt;

}

inline void prepare()

{

	fac[0]=1;

	rep(1,maxx,i)fac[i]=fac[i-1]*i%mod;

	inv[maxx]=ksm(fac[maxx],mod-2);

	for(int i=maxx-1;i>=0;--i)inv[i]=inv[i+1]*(i+1)%mod;

}

inline ll C(int a,int b)

{

	if(a<b)return 0;

	return fac[a]*inv[b]%mod*inv[a-b]%mod;

}

int main()

{

	//freopen("1.in","r",stdin);

	get(n);get(m);get(c);

	rep(1,c,i)get(a[i]),mx=max(mx,a[i]),vis[a[i]]=1;

	maxx=n*m;prepare();

	f[0][0][0]=1;g[0][0][0]=1;

	rep(1,mx,i)

	{

		if(!vis[i])continue;

		rep(1,n,j)rep(1,m,k)

		{

			if(i<j||i<k)continue;

			rep(1,j,w1)rep(1,k,w2)

			{

				if(w1==j&&k==w2)g[i][j][k]=(g[i][j][k]+C(j*k,i))%mod;

				else g[i][j][k]=(g[i][j][k]-C(j,w1)*C(k,w2)%mod*g[i][w1][w2]%mod)%mod;

			}

		}

	}

	rep(1,c,i)//前i种颜色

	{

		rep(0,n,j)rep(0,m,k)

		{

			if(!f[i-1][j][k])continue;

			rep(1,n-j,l)rep(1,m-k,r)

			{

				if(a[i]<l||a[i]<r)continue;

				f[i][j+l][k+r]=(f[i][j+l][k+r]+C(n-j,l)*C(m-k,r)%mod*f[i-1][j][k]%mod*g[a[i]][l][r]%mod)%mod;

			}

		}

	}

	rep(1,n,j)rep(1,m,k)ans=(ans+f[c][j][k])%mod;

	printf("%lld\n",(ans+mod)%mod);

	return 0;

}

巴特西

luogu 3158 [CQOI2011]放棋子

最新文章

热门文章