题目链接:https://vjudge.net/problem/UVA-10601
题目大意:
见刘汝佳《算法竞赛入门经典——训练指南》(P182).
知识点: 组合计数、置换群
解题思路:
正方体的置换有(4)种:
(A). 静止不动((1) 个)。置换类型为 ((12,0,0,0,0,0)).( ((a,b,c,d,e,f)) 表示其置换表达式是一个有 (a) 个一阶循环,(b) 个二阶循环,(c) 个三阶循环......(依次类推),详见《组合数学(原书第五版)》)。
(B). 以一个面的中心到其对面中心的连线为轴旋转((3) 条轴)
旋转 (90cir),置换类型为 ((0,0,0,3,0,0));
旋转 (180cir),置换类型为 ((0,6,0,0,0,0));
旋转 (270cir),置换类型为 ((0,0,0,3,0,0))。
(C). 以两个对顶点的连线为轴旋转((4) 条轴)
旋转 (120cir),置换类型为 ((0,0,4,0,0,0));
旋转 (240cir),置换类型为 ((0,0,4,0,0,0))。
(D). 以两条对边的中点的连线为轴旋转((6) 条轴)
旋转 (180cir),置换类型为 ((2,5,0,0,0,0))。
不难发现:除了 (D) 类置换之外,其他所有置换的循环长度都是单一的,在计算不变着色数时,对于每一种木棍的数量 (n),如果不整除循环长度 (k),说明不变着色数为(0),否则就是种类数就是 (C_{12/k}^{n/k});对于 (D) 类置换,枚举两个一阶循环的着色情况,其他的处理方式同上。
AC代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 ll a[7],b[7]; 6 ll C[20][20]; 7 void init(){ 8 C[0][0]=C[1][0]=C[1][1]=1; 9 for(int i=2;i<20;i++){ 10 C[i][0]=C[i][i]=1; 11 for(int j=1;j<i;j++) 12 C[i][j]=C[i-1][j-1]+C[i-1][j]; 13 } 14 } 15 ll cal(int n,int tot){ //(循环长度,总循环数) 16 for(int i=1;i<=6;i++){ 17 if(b[i]%n!=0) return 0; 18 b[i]/=n; //每种木棍可以填满的循环数 19 } 20 ll ret=1; 21 for(int i=1;i<=6;i++){ 22 ret*=C[tot][b[i]]; 23 tot-=b[i]; //总循环数要相应地减去 24 } 25 return ret; 26 } 27 int main(){ 28 init(); 29 int t; 30 scanf("%d",&t); 31 while(t--){ 32 memset(a,0,sizeof(a)); 33 int tmp; 34 for(int i=0;i<12;i++){ 35 scanf("%d",&tmp); 36 a[tmp]++; 37 } 38 ll ans=0; 39 for(int i=1;i<=6;i++) b[i]=a[i]; 40 ans+=cal(4,3)*6; 41 for(int i=1;i<=6;i++) b[i]=a[i]; 42 ans+=cal(2,6)*3; 43 for(int i=1;i<=6;i++) b[i]=a[i]; 44 ans+=cal(3,4)*8; 45 for(int i=1;i<=6;i++) b[i]=a[i]; 46 ans+=cal(1,12); 47 for(int i=1;i<=6;i++){ 48 for(int j=1;j<=6;j++){ 49 for(int k=1;k<=6;k++) b[k]=a[k]; 50 b[i]--,b[j]--; 51 if(b[i]<0||b[j]<0) continue; 52 ans+=cal(2,5)*6; 53 } 54 } 55 printf("%lld ",ans/24); //共24个置换 56 } 57 return 0; 58 }