题解：P17096 [ICPC 2017 Qingdao R] Floppy Cube
lailai0916
·
·
题解
题意简述
给 Floppy Cube 的 30 个贴纸面任意染上 n 种颜色。
若两种染色能通过机械允许的转棱或整体旋转互相得到，
则把它们视为同一种方案。
求本质不同的染色数对任意给定的 P 取模。
解题思路
把 30 个贴纸面固定编号。
任意一次合法操作都会置换这些编号，
所有合法操作组成一个作用在 30 个位置上的置换群 G。
这个群可以离线完整枚举。
用小块在 1\times3\times3 平面内的坐标，
以及贴纸面的单位法向量共同描述一个贴纸位置。
准备以下三类生成元：
- 绕垂直于大面的轴整体旋转 90^\circ；
- 绕大面内的一条对称轴整体旋转 180^\circ；
- 绕一条边块执行题目允许的 180^\circ 转动。
前两个生成元产生长方体的全部整体旋转。
第三个生成元经过这些整体旋转共轭后，
可以得到对任意边块的转动。
因此，它们生成的闭包恰好是全部机械可达状态。
从单位置换开始，对三个生成元进行广度优先搜索，
可以得到：
|G|=1536
对于一个置换 g，记其置换环数为 c(g)。
一种染色被 g 保持不变，
当且仅当每个置换环内的贴纸颜色相同。
每个环可以独立选择一种颜色，所以固定染色数为：
n^{c(g)}
由 Burnside 引理，本质不同的染色数为：
\frac{1}{1536}\sum_{g\in G}n^{c(g)}
枚举群元素并统计置换环后，得到如下分布：
| 环数 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 个数 |
128 |
144 |
128 |
120 |
64 |
216 |
108 |
72 |
| 环数 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
| 个数 |
176 |
24 |
55 |
72 |
66 |
72 |
15 |
24 |
| 环数 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
| 个数 |
16 |
24 |
5 |
0 |
6 |
0 |
1 |
表中个数之和为 1536，与群大小一致。
于是 Burnside 分子是固定多项式：
S(n)=\sum_{i=0}^{30}\operatorname{cnt}_i n^i
代码把这 31 个系数写入常量数组，
并从高次到低次使用秦九韶算法求值。
还需处理模数 P 与 1536 不互质的情况。
不能把除以 1536 改成乘模逆元。
改为先计算：
r=S(n)\bmod(1536P)
Burnside 引理保证 S(n) 能被 1536 整除。
又因为 S(n)-r 是 1536P 的倍数，
设真实答案为 $A=S(n)/1536$，则：
$$
A-\frac{r}{1536}
=\frac{S(n)-r}{1536}
$$
右侧是 $P$ 的倍数，
所以 $r/1536$ 正是 $A\bmod P$。
最大中间模数为 $1536P$，仍能装入 64 位整数；
秦九韶乘法使用 128 位整数避免乘积溢出。
每组询问只进行 $31$ 次转移，时间复杂度为 $O(30)$，空间复杂度为 $O(1)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128_t;
const int G=1536;
const int cnt[31]={0,0,0,0,0,0,0,0,128,144,128,120,64,216,108,72,176,24,55,72,66,72,15,24,16,24,5,0,6,0,1};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n,p;
cin>>n>>p;
ll mod=(ll)p*G;
ll ans=0;
for(int i=30;i>=0;i--)ans=ll(((i128)ans*n+cnt[i])%mod);
cout<<ans/G<<'\n';
}
return 0;
}
```