自动搬运

查看原文

来自洛谷，原作者为

	HenryHuang 单程孤舟，出云入霞，如歌如吟。

搬运于2025-08-24 22:10:56，当前版本为作者最后更新于2019-10-02 21:17:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5456 「THUPC2018」蛋糕 题解

这个题目退化成三维就是我们小学时经常做的题目，应该都可以背结论了

我们先从三维开始嘶烤，设三维空间的大小为 $a*b*c$

如果涂了0面，就相当于三个方向上都没有碰到边界，答案为 $(a-2)*(b-2)*(c-2)$

如果涂了1面，就相当于有一个方向碰到了边界，答案为 $2*((a-2)*(b-2)+(b-2)*(c-2)+(a-2)*(c-2))$

如果涂了2面，就相当于有两个方向碰到了边界

如果涂了3面，就相当于有三个方向碰到了边界

以此类推，四维也挺好做的，直接DFS即可

贴代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2148473648;
ll f[10],a[10];
void dfs(ll now,ll tot,ll num){
	if(now==5){
		f[tot]=(f[tot]+num)%mod;//枚举完毕 
		return ;
	}
	if(a[now]==1){
		dfs(now+1,tot+2,num);
		return ;
	}//如果是1特殊处理 
	dfs(now+1,tot+1,(num+num)%mod);//不选 
	dfs(now+1,tot,(num*(a[now]-2))%mod);//选 
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(f,0,sizeof f);
		for(int i=1;i<=4;++i) scanf("%lld",&a[i]);
		dfs(1,0,1);
		for(int i=0;i<=8;++i)
			printf("%lld ",f[i]);
		printf("\n");
	}
}