题解 P5456 【[THUPC2018]蛋糕】

· · 题解

一开始做这道题的时候有点懵，在网上能找到的题解几乎都是dfs，蒟蒻不太懂这种做法，于是摸索半天推了个规律。

这道题放在了组合计数专题的例题中，开始的时候其实我没感觉这道题跟组合数有多大关系，后来想想，如果把四维换成n维，就是标准的组合计数了。

分析

这道题求的是四维的情况，直接做似乎不可行？不妨先考虑三维的情况，那么这道题就退化成了一个小学数学题：有一个由1*1*1的小立方体构成的a*b*c的大立方体，给这个大立方体的表面涂上颜色，求被涂了0,1,2,3,4面的小立方体各有多少个。

Ⅰ.考虑a,b,c都>=2的情况（三维物体中0个维度为1），那么就不存在被涂了4面的小正方体，用ans[i]表示被涂了i面的小立方体数量，那么三维规律即为:

ans[0]=(a-2)*(b-2)*(c-2) ans[1]=2*((a-2)*(b-2)+(a-2)*(c-2)+(b-2)*(c-2)) ans[2]=4*((a-2)*(b-2)*(c-2)) ans[3]=8

其余皆为0。

Ⅱ.如果a,b,c中就有那么个不开眼的为1呢（三维物体中1个维度为1）？假设c=1，那么规律即为:

ans[2]=(a-2)*(b-2) ans[3]=2*(a+b-4) ans[4]=4

其余皆为0。

Ⅲ.如果a,b,c中有两个不开眼的为1呢（三维物体中2个维度为1）？我们假设b=c=1，那么规律即为：

ans[4]=a-2 ans[5]=2

其余皆为0。

Ⅳ.如果a,b,c皆为0呢（三维物体中有3个维度为1）？

ans[6]=1

其余皆为0。

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

那么四维怎么办呢？仍然按照有0,1,2,3,4个维度为1来分类讨论。

先define一波。

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

Ⅰ.四维物体有0个维度为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，相当于三维物体有0个维度为1，那么可以进行规律转换，只不过要注意，ans[i]的下标要加上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个维度为1，相当于三维物体有1个维度为1

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

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

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

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

ans[8]=1;

直到这里，我们就推导出了完整的规律。

本质上跟dfs差不多...

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
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()
{
//  freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
    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]);     
            continue;   
        }
        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]);
            continue;   
        }
        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]);
            continue;           
        }
        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]);
            continue;
        }
        if(cnt==0)
        {
            ans[8]=1;
            for(int i=0;i<=8;i++)
            printf("%lld ",ans[i]);
            continue;
        }
    }
    return 0;
}

扩展

其实这道题过水了，完全可以扩展到N维的情况，规律都是相同的，只有转换到N维，才能体现出这道题的组合数思想，大家可以思考一下通解&更优解法，反正我只会暴力qwq。

组合计数txdy!