CodeVS 2926 黑白瓷砖：Polya 计数定理应用

题目大意

正三角形区域由小三角形组成，第 n 层有 n(n+1)/2 个小三角形。每个小三角形黑/白染色。两种染色若可通过旋转/翻转重合视为相同。求本质不同染色数。

置换群分析（D₃ 群，6 个对称操作）

1. 恒等变换：1 个
2. 旋转 120°：1 个
3. 旋转 240°：1 个
4. 三条对称轴翻转：3 个

循环指数计算

• 总点数 S = n(n+1)/2
• 旋转：每个循环 3 个点 → 循环数 (S+2)/3
• 翻转：中轴线上 (n+1)/2 个点各自成循环，其余配对 → 循环数 (S + (n+1)/2)/2
• 恒等：S 个循环

Polya 公式

Ans = (2^S + 2·2^{(S+2)/3} + 3·2^{(S+(n+1)/2)/2}) / 6

C++ 实现

#include 
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int S = n*(n+1)/2;
    int m = (S + (n+1)/2) / 2; // 翻转循环数
    // 注：需高精度，此处略
    printf("%d\n", (2*(1<<((S+2)/3)) + 3*(1<

关键点

群封闭性：必须包含所有复合操作（旋转+翻转生成斜向翻转）
循环计数：几何归纳得公式
高精度：n 较大时 2^S 超长，需大整数库