题解：P12002 吃猫粮的玉桂狗

好题。

题目的意思就是一些东西有个数限制，要把东西丢到树上，然后有几个东西不能按照某种顺序摆。

考虑容斥。

我们先放弃这个个数限制，先算出这种情况下的答案数。

显然，每个点只要记录下这个点是某个颜色的方案数，转移只要把符合条件的儿子乘起来就好了。这一部分是

O(n^4)

的。

代码如下。

CPP

void dfs1(int x,int fa){
	if(g[x].size()==1&&fa){
		for(int i=1;i<=m;i++)dp[x][i][0]=1;
	} 
	for(int i:g[x]){
		if(i==fa)continue;
		dfs1(i,x);
		for(int j=1;j<=m;j++){
			ll tmp=0;
			for(int k=1;k<=m;k++){
				if(!s[j][k]){
					if(dp[x][j][0]==0&&dp[i][k][0]!=0)dp[x][j][0]=1;
					tmp+=dp[i][k][0];
					tmp%=mod;
				}
			}
			dp[x][j][0]*=tmp;
			dp[x][j][0]%=mod;
		}
	}
}

然后考虑某个东西个数不够的情况，显然这个东西我们不能直接容斥，不然就爆了，但是题目有个条件还没用到，就是

c_i\ge\frac{n}{2}

，这个东西有啥用呢？就是没有两个东西同时用超过的情况，否则放的东西就比

n

还多了。

所以我们可以枚举下每个超出的物品

i

，然后每个点记录下这个点的颜色，和

i

的个数。

朴素的 dp 是

O(n^6)

的，代码长这样。

CPP

void dfs2(int x,int fa){
	for(int i=1;i<=m;i++)dp[x][i][0]=1;
	for(int i:g[x]){
		if(i==fa)continue;
		dfs2(i,x);
		ll f[N][N]={0};
		for(int j=1;j<=m;j++){
			for(int k=0;k<=n;k++){//当前节点的颜色和标记数量 
				int tmp=0;
				for(int l2=0;l2<=k;l2++){
					for(int l=1;l<=m;l++){
						if(s[j][l])continue;
						f[j][k]+=dp[x][j][k-l2]*dp[i][l][l2];
					}
				}
			}
		}
		for(int j=1;j<=m;j++)for(int k=0;k<=n;k++)dp[x][j][k]=f[j][k];
	}
	for(int j=n;j>=1;j--)dp[x][mark][j]=dp[x][mark][j-1];
	dp[x][mark][0]=0;
}

考虑如何优化这玩意，其实就是因为枚举每个点使用被标记的东西的个数，导致了统计多次儿子对某个东西的贡献，所以这玩意先与处理下直接用即可，复杂度

O(n^5)

。

代码如下。

CPP

void dfs2(int x,int fa){
	for(int i=1;i<=m;i++)dp[x][i][0]=1;
	for(int i:g[x]){
		if(i==fa)continue;
		dfs2(i,x);
		ll f[N][N]={0};
		for(int j=1;j<=m;j++){
			for(int k=0;k<=n;k++){//当前节点的颜色和标记数量 
				int tmp=0;
				for(int l2=0;l2<=k;l2++){
					f[j][k]+=dp[x][j][k-l2]*summ[i][j][l2]%mod;
					f[j][k]%=mod;
				}
			}
		}
		for(int j=1;j<=m;j++)for(int k=0;k<=n;k++)dp[x][j][k]=f[j][k];
	}
	for(int j=n;j>=1;j--)dp[x][mark][j]=dp[x][mark][j-1];
	dp[x][mark][0]=0;
	for(int j=1;j<=m;j++){
		for(int k=0;k<=n;k++){
			for(int l=1;l<=m;l++){
				if(s[j][l])continue;
				summ[x][j][k]+=dp[x][l][k];
			}
		}
	}
}

题解：P12002 吃猫粮的玉桂狗

文章操作

相关推荐

评论

题解：P12002 吃猫粮的玉桂狗