[THUPC2018]蛋糕solution

题目描述

最近，菲菲学会了做蛋糕，她做了一个4D的蛋糕送给牛牛，这个蛋糕的大小是：$a \times b \times c \times d$a×b×c×d。

蛋糕所有的表面都抹着奶油，牛牛想把蛋糕沿着与表面平行的超平面，切成$1 \times 1 \times 1 \times 1$1×1×1×1的小块。

现在，牛牛想知道，在这些小块蛋糕中，有$0$0个、$1$1个、$2$2个$\cdots\cdots$⋯⋯$8$8个表面抹着奶油的有分别有多少块。

题目大意

一个$a\times b\times c\times d$a×b×c×d的4D图形，对每个表面染色，问被染$0$0面、$1$1面、$2$2面$\cdots\cdots 8$⋯⋯8面的块分别有几个。

解题思路

第①​种解法

考虑当前第$i$i维，最上面和最下面$2$2个$i-1$i−1维的图形会减少$1$1个被染色的面。 剩下$l_i-2$li​−2个图形会减少$2$2个被染色的面。

这幅图中，维度$i$i是$3$3，假设图形$1,2$1,2是$2$2维图形，那么图形$1$1的下面被覆盖，减少了$1$1个被染色的面。 图形$2$2的上下面都被覆盖，减少了$2$2个被染色的面。

算法是$DFS$DFS，从第$4$4维一直到第$0$0维计算答案。

当构成图形的某个长$l_i$li​为$1$1时需进行特判，这时增加的个数应该是$i-1$i−1维时的个数，因为$1\times x=x$1×x=x，相当于$i-1$i−1维。

代码实现

#include<bits/stdc++.h>
typedef long long ll;//防止计算溢出
int T,l[10];
ll a[10];
#define p 2148473648//原题中要对2148473648取模
void dfs(int t,ll s,int m){//t表示当前维度，s表示对m面染色能增加的个数，m表示当前计算的染色面数
    if(!t)return void((a[m]+=s)%=p);//当t为0维度，增加答案
    if(l[t]==1)return dfs(t-1,s,m);//特判长度为1时增加的个数
    dfs(t-1,s*2%p,m-1);//第i维的最上最下2个i-1维的图形
    dfs(t-1,s*(l[t]-2)%p,m-2);//第i维中间的l-2个图形
}
int main(){
    for(scanf("%d",&T);T--;){
        scanf("%d%d%d%d",&l[1],&l[2],&l[3],&l[4]),dfs(4,1,8);//从第4维倒推
        for(int i=0;i<=8;i++)printf("%lld%c",a[i],i==8?'\n':' '),a[i]=0;
    }
    return 0;
}

第②种解法

推导过程

由于注意到本题只有$4$4维，数据不大，可以手玩推公式。

直接$4$4维计算较难理解，所以先推一下小学就学过的$3$3维染色个数的公式。

题目为：有一个由$1\times 1\times 1$1×1×1的小立方体构成的$a\times b\times c$a×b×c的大立方体，给这个大立方体的表面涂上颜色，求被涂了$0,1,2,3,4$0,1,2,3,4面的小立方体各有多少个。

• Ⅰ.考虑$a,b,c\geq 2$a,b,c≥2的情况（三维图形中$0$0个维度为$1$1），所以不存在被涂了$4$4面的小正方体，用$ans_i$ansi​表示被涂了$i$i面的小立方体数量，那么规律为:
  $ans_0=(a-2)\times(b-2)\times(c-2)\\ ans_1=2\times((a-2)\times(b-2)+(a-2)\times(c-2)+(b-2)\times(c-2))\\ ans_2=4\times((a-2)\times(b-2)\times(c-2))\\ ans_3=8\\ ans_x=0\ (x>3)$ans0​=(a−2)×(b−2)×(c−2)ans1​=2×((a−2)×(b−2)+(a−2)×(c−2)+(b−2)×(c−2))ans2​=4×((a−2)×(b−2)×(c−2))ans3​=8ansx​=0 (x>3)

• Ⅱ.如果$a,b,c$a,b,c中假设$c=1$c=1（三维图形中$1$1个维度为$1$1），那么规律为:
  $ans_0=ans_1=0\\ans_2=(a-2)\times(b-2)\\ans_3=2\times(a+b-4)\\ans_4=4\\ ans_x=0\ (x>4)$ans0​=ans1​=0ans2​=(a−2)×(b−2)ans3​=2×(a+b−4)ans4​=4ansx​=0 (x>4)

• Ⅲ.如果$a,b,c$a,b,c中假设$b,c=1$b,c=1（三维图形中$2$2个维度为$1$1），那么规律为:
  $ans_0=ans_1=ans_2=ans_3=0\\ans_4=a-2\\ans_5=2\\ans_x=0\ (x>5)$ans0​=ans1​=ans2​=ans3​=0ans4​=a−2ans5​=2ansx​=0 (x>5)

• Ⅳ.如果$a,b,c=1$a,b,c=1（三维图形中$3$3个维度为$1$1），那么规律为:
  $ans_0=ans_1=ans_2=ans_3=ans_4=ans_5=0\\ans_6=1\\ans_x=0\ (x>6)$ans0​=ans1​=ans2​=ans3​=ans4​=ans5​=0ans6​=1ansx​=0 (x>6)

以上推出了三维物体的全部规律。

然后我们考虑四维，按照有$0,1,2,3,4$0,1,2,3,4个维度为$1$1来分类讨论。

方便计算，先$define$define。

#define A (a-2)%mod
#define B (b-2)%mod
#define C (c-2)%mod
#define D (d-2)%mod

Ⅰ.四维物体有$0$0个维度为$1$1

ans[0]=A*B*C*D;
ans[1]=2*(A*B*C+A*B*D+A*C*D+B*C*D)%mod;
ans[2]=4*(A*B+A*C+A*D+B*C+B*D+C*D)%mod;
ans[3]=8*(A+B+C+D)%mod;
ans[4]=16;

Ⅱ.四维物体有$1$1个维度为$1$1，相当于三维物体有$1$1个维度为$1$1，那么可以进行规律转换，只不过要注意， $ans_i$ansi​的下标要加上2 ，因为我们增加了一维。

ans[2]=A*B*C%mod;
ans[3]=2*(A*B+A*C+B*C)%mod;
ans[4]=4*(A+B+C)%mod;
ans[5]=8;

Ⅲ.四维物体有$2$2个维度为$1$1，相当于三维物体有$1$1个维度为$1$1。

ans[4]=(a-2)*(b-2)%mod;
ans[5]=2*(a+b-4)%mod;
ans[6]=4;

Ⅳ.四维物体有$3$3个维度为$1$1，相当于三维物体有$2$2个维度为$1$1。

ans[6]=(a%mod-2%mod)%mod;
ans[7]=2;

Ⅴ.四维物体有$4$4个维度为$1$1，相当于三维物体有$3$3个维度为$1$1。

ans[8]=1;

到这里，四维图形的公式就推导完了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=2148473648;
#define A (a-2)%mod
#define B (b-2)%mod
#define C (c-2)%mod
#define D (d-2)%mod
int ans[9],a,b,c,d,cnt,f[5];
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        memset(ans,0,sizeof ans);
        memset(f,0,sizeof f);
        cnt=0;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        if(a!=1)f[++cnt]=a;
        if(b!=1)f[++cnt]=b;
        if(c!=1)f[++cnt]=c;
        if(d!=1)f[++cnt]=d;
        if(cnt==4){
            ans[0]=A*B*C*D;
            ans[1]=2*(A*B*C+A*B*D+A*C*D+B*C*D)%mod;
            ans[2]=4*(A*B+A*C+A*D+B*C+B*D+C*D)%mod;
            ans[3]=8*(A+B+C+D)%mod;
            ans[4]=16;
            for(int i=0;i<=8;i++)printf("%lld ",ans[i]);     
        }
        if(cnt==3){
            a=f[1],b=f[2],c=f[3];
            ans[2]=A*B*C%mod;
            ans[3]=2*(A*B+A*C+B*C)%mod;
            ans[4]=4*(A+B+C)%mod;
            ans[5]=8;
            for(int i=0;i<=8;i++)printf("%lld ",ans[i]);
        }
        if(cnt==2){
            a=f[1],b=f[2];
            ans[4]=(a-2)*(b-2)%mod;
            ans[5]=2*(a+b-4)%mod;
            ans[6]=4;
            for(int i=0;i<=8;i++)printf("%lld ",ans[i]);       
        }
        if(cnt==1){
            a=f[1];
            ans[6]=(a%mod-2%mod)%mod;
            ans[7]=2;
            for(int i=0;i<=8;i++)printf("%lld ",ans[i]);
        }
        if(cnt==0){
            ans[8]=1;
            for(int i=0;i<=8;i++)printf("%lld ",ans[i]);
        }
        printf("\n");
    }
    return 0;
}