专栏文章

题解：P5456 [THUPC 2018] 蛋糕

ppengziyippp
P5456题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioxylk1
此快照首次捕获于
2025/12/03 02:58
3 个月前
此快照最后确认于
2025/12/03 02:58
3 个月前
查看原文

题目大意

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

思路简述

实话说这个题目我看了好几遍都没能抽象地理解 4D。
既然理解不了，那我们就先考虑将四维转换为我们熟悉的三维探究。
可以将蛋糕抽象的想象成一个魔方。
容易得出结论，在大多数情况下，小蛋糕最多被覆盖 33 面，最少被覆盖 00 面。33 面即为角块，22 面即为棱块，11 面即为中心块，00 面即为最中间里面的部分。
由此可推出，
ans[0]=(a−2)×(b−2)×(c−2);ans[0] = (a - 2)\times(b - 2)\times(c - 2);
ans[1]=2×((a−2)×(b−2)+(a−2)×(c−2)+(b−2)×(c−2));ans[1] = 2\times((a - 2)\times(b - 2) + (a - 2)\times(c - 2) + (b - 2)\times(c - 2));
ans[2]=4×((a−2)+(b−2)+(c−2));ans[2] = 4\times((a - 2) + (b - 2) + (c - 2));
ans[3]=8;ans[3] = 8;
当然，以上只存在于 a,b,c≥2a,b,c \ge 2 的情况下。
其他的情况如 a,b,ca,b,c 有其中一个为 11 时，我们可以视为物体由三维降到二维，由此不难类推出满足 a,b,c<2a,b,c<2 有 11 个，22 个，33 个时的公式，均与上述相似。
而题目所要求的四维情况，相当于如上再加上一个维度。
看看代码中的实现就不难理解其中的规律了 !!
最后要记得模，不然容易爆炸。
结束撒花。

代码实现

马蜂良好。
CPP
#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();
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...