UVA 10601 Cubes：波利亞計數求染色立方體棱本質不同方案數

題目大意

12 條棱，每條有指定顏色（1~6）。用這 12 條棱組裝立方體，旋轉相同視為一種。求本質不同組裝數。

波利亞計數於棱集合

立方體旋轉群 24 元素作用於 12 條棱，循環結構分類：

固定染色數 = 顏色數 ^ 循環數。但本題顏色有重複（給定 12 條棱的顏色多重集），需用生成函數或組合計算每類旋轉的固定染色數。

代碼實現：組合計算固定染色數

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

ll C[15][15];
int a[15], b[15];  // a: 原始顏色計數, b: 複製用

void init() {
    for (int i=0; i<=12; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j=1; j

關鍵邏輯解析

solve(k)：計算所有循環長度為 k 的置換固定染色數。需每種顏色計數能被 k 整除，否則 0。否則為多重組合數：(n)! / (c1! c2! ...)，用組合數連乘計算
still()：恆等置換，循環長度 1，solve(1)
point()：對角軸 ±120°，8 個，循環長度 3，8 * solve(3)
plane()：面心軸：3 個 180° (循環長度 2) + 6 個 90° (循環長度 4)，3*2*solve(2) + 3*solve(4)（代碼中合併計算）
edge()：棱心軸 180°，固定 2 條棱（循環長度 1），其餘 10 條成 5 個 2-循環。枚舉固定的 2 條棱顏色組合，6 * solve(2)


樣例驗證

輸入：1 2 2 2 2 2 2 2 2 2 2 2 → 輸出 1
輸入：1 1 2 2 2 2 2 2 2 2 2 2 → 輸出 5
輸入：1 1 2 2 3 3 4 4 5 5 6 6 → 輸出 312120


此題是波利亞計數在「有重複顏色、作用於棱」上的綜合應用，代碼通過組合數計算每類旋轉的固定染色數，體現了組合數學與編程的深度結合。