P5456 「THUPC2018」蛋糕 题解

· · 题解

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");
    }
}