Cubes

題意

給出$12$根長度相等的木棒,顏色最多有$6$種,問能構成的本質不同的正方體數量.

題解

根據波利亞定理公式:

設X是元素集合,G是X的置換群,$\{u_1,u_2,...,u_k\}$是$k$種顏色的集合,$C$是$X$的任意著色集.這時,針對各顏色的數目的C的非等價著色數的生成函數是:
$P_G(u_1+...+u_k,u_1^2+...+u_k^2,...,u_1^n+...+u_k^n)$

我們先求出$12$根木棒的顏色數,假設有$k$中,每種顏色假設有$\{c_1,c_2,...,c_k\}$個,注意$c_1+...+c_k=12$.

求出置換群.
眾所周知的,正方體的置換群大小是$24$.
(1)恒等變換:$1$個
(2)繞對面的中心旋轉$90,180,270$度:$3?3=9$個.
(3)繞對邊的中點連成的軸旋轉$180$度:$6?1=6$個.
(4)繞體對角線旋轉$120,240$度:$4?2=8$個.
根據上述四種情況得到的關于線元素的置換平均值為:
$P_G=\frac{1}{24}(z_1^{12}+6z_4^3+3z_2^6+8z_3^4+6z_1^2{z}_2^5)$

將$z_i=\sum u_1^i{u}_2^i...u_6^i$代入$P_G$式.那么答案就是$P_G$函數的$u_1^{c_1}{u}_2^{c_2}...u_k^{c_k}$前的系數

$P_G$函數的每一項都是形如$(u_1+...+u_k{)}^a(u_1^2+...+u_k^2{)}^b...(u_1^n+...+u_k^n{)}^z$的,我要對每個這樣的式子,求$u_1^a{u}_2^b...u_k^z$前的系數之和.每個項單獨進行$dfs$就可以了.

代碼

#include <iostream> #include <algorithm> #include <map> #include <cstring> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i)int T; int tc[7],x[7],ox[7]; int C[13][13];void init() {C[0][0] = 1;rep(i,1,12) {C[i][0] = 1;rep(j,1,i) {C[i][j] = C[i-1][j] + C[i-1][j-1];}} } int ans = 0; void dfs(int dep,int mul) {if(dep == 5) {int f = 0;rep(i,1,6) f += x[i];if(!f) {ans += mul;}return ;}int tx[7];rep(i,1,6) tx[i] = x[i];for(int x1 = 0;x1 <= tc[dep] && dep * x1 <= tx[1];++x1) {int res1 = C[tc[dep]][x1];for(int x2 = 0;x2 <= tc[dep] - x1 && dep*x2 <= tx[2];++x2) {int res2 = res1 * C[tc[dep]-x1][x2];for(int x3 = 0;x3 <= tc[dep]-x1-x2 && dep*x3 <= tx[3];++x3) {int res3 = res2 * C[tc[dep]-x1-x2][x3];for(int x4 = 0;x4 <= tc[dep]-x1-x2-x3 && dep*x4 <= tx[4];++x4) {int res4 = res3 * C[tc[dep]-x1-x2-x3][x4];for(int x5 = 0;x5 <= tc[dep]-x1-x2-x3-x4 && dep*x5 <= tx[5];++x5) {int res5 = res4 * C[tc[dep]-x1-x2-x3-x4][x5];int x6 = tc[dep]-x1-x2-x3-x4-x5;//pr(x1);pr(x2);pr(x3);pr(x4);pr(x5);pr(x6);if(dep*x6 <= tx[6]) {x[1] = tx[1] - dep*x1;x[2] = tx[2] - dep*x2;x[3] = tx[3] - dep*x3;x[4] = tx[4] - dep*x4;x[5] = tx[5] - dep*x5;x[6] = tx[6] - dep*x6;dfs(dep+1,res5*mul);}}}}}} }int main() {init();std::ios::sync_with_stdio(false);std::cin >> T;while(T--) {memset(ox,0,sizeof(ox));rep(i,1,12) {int tmp;std::cin >> tmp;ox[tmp] ++;}int res = 0;rep(i,1,6) x[i] = ox[i];ans = 0;tc[1] = 12,tc[2] = tc[3] = tc[4] = 0;dfs(1,1);res += ans;rep(i,1,6) x[i] = ox[i];ans = 0;tc[1] = tc[2] = tc[3] = 0,tc[4] = 3;dfs(1,1);res += 6*ans;rep(i,1,6) x[i] = ox[i];ans = 0;tc[1] = tc[3] = tc[4] = 0,tc[2] = 6;dfs(1,1);res += 3*ans;rep(i,1,6) x[i] = ox[i];ans = 0;tc[1] = tc[2] = tc[4] = 0,tc[3] = 4;dfs(1,1);res += 8*ans;rep(i,1,6) x[i] = ox[i];ans = 0;tc[1] = 2,tc[2] = 5,tc[3] = tc[4] = 0;dfs(1,1);res += 6*ans;std::cout << res/24 << std::endl;}return 0; }

總結

以上是生活随笔為你收集整理的UVA10601 Cubes - 波利亚定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。