题解：P5456 [THUPC 2018] 蛋糕

· · 题解

题目大意

给出一个 4D 的蛋糕的各边长 a,b,c,d。
求出有 0\sim8 面为外层涂有奶油的 1\times1\times1\times1 小蛋糕各有多少个。

思路简述

实话说这个题目我看了好几遍都没能抽象地理解 4D。
既然理解不了，那我们就先考虑将四维转换为我们熟悉的三维探究。
可以将蛋糕抽象的想象成一个魔方。
容易得出结论，在大多数情况下，小蛋糕最多被覆盖 3 面，最少被覆盖 0 面。3 面即为角块，2 面即为棱块，1 面即为中心块，0 面即为最中间里面的部分。
由此可推出，

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) + (b - 2) + (c - 2)); ans[3] = 8;

当然，以上只存在于 a,b,c \ge 2 的情况下。
其他的情况如 a,b,c 有其中一个为 1 时，我们可以视为物体由三维降到二维，由此不难类推出满足 a,b,c<2 有 1 个，2 个，3 个时的公式，均与上述相似。
而题目所要求的四维情况，相当于如上再加上一个维度。
看看代码中的实现就不难理解其中的规律了 !
最后要记得模，不然容易爆炸。
结束撒花。

代码实现

马蜂良好。 

#include<bits/stdc++.h>
#define int long long
#define mod 2148473648
using namespace std;
const int N = 10;
int f[N], ans[N];
int a, b, c, d, tot; 
void solve () {
    memset (ans, 0, sizeof (ans));
    memset (f, 0, sizeof (f)); // 初始化很重要！
    tot = 0;
    cin >> a >> b >> c >> d;
    if (a >= 2) f[++tot] = a; if (b >= 2) f[++tot] = b;
    if (c >= 2) f[++tot] = c; if (d >= 2) f[++tot] = d; // 统计
    if (tot == 0) {
        ans[8] = 1;
    } else if (tot == 1) {
        int t1 = f[1] - 2;
        ans[7] = 2;
        ans[6] = t1 % mod;
    } else if (tot == 2) {
        int t1 = f[1] - 2, t2 = f[2] - 2;
        ans[6] = 4;
        ans[5] = 2 * (t1 + t2) % mod;
        ans[4] = (t1 * t2) % mod;
    } else if (tot == 3) {
        int t1 = f[1] - 2, t2 = f[2] - 2, t3 = f[3] - 2;
        ans[5] = 8;
        ans[4] = 4 * (t1 + t2 + t3) % mod;
        ans[3] = 2 * ((t1 * t2) % mod + (t1 * t3) % mod + (t3 * t2) % mod) % mod;
        ans[2] = (((t1 * t2) % mod) * t3) % mod;
    } else {
        int t1 = f[1] - 2, t2 = f[2] - 2, t3 = f[3] - 2, t4 = f[4] - 2;
        ans[4] = 16;
        ans[3] = 8 * (t1 + t2 + t3 + t4) % mod;
        ans[2] = 4 * ((t1 * t2) % mod + (t1 * t3) % mod + (t1 * t4) % mod + (t2 * t3) % mod + (t2 * t4) % mod + (t3 * t4) % mod) % mod;
        ans[1] = 2 * (((t1 * t2) % mod * t3) % mod + ((t1 * t2) % mod * t4) % mod + ((t1 * t3) % mod * t4) % mod + ((t4 * t2) % mod * t3) % mod) % mod;
        ans[0] = (((t1 * t2) % mod * t3) % mod * t4) % mod;
    }
    for (int i = 0; i <= 8; i ++ ) {
        cout << ans[i] % mod << " ";
    }
    cout << "\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) {
        solve();
    }
}