UVa 10601 (Polya计数 等价类计数) Cubes

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 #include <cassert>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 int a[7], b[7];
 9 const int maxn = 12;
10 LL C[15][15];
11 
12 LL cal(int k)//k为循环节长度
13 {
14     LL ans = 1;
15     vector<int> t;
16     int num = 0; //num为循环节的个数
17     for(int i = 0; i < 6; i++)
18     {
19         if(a[i] % k == 0) { t.push_back(a[i]/k); num += a[i]/k; }
20         else return 0;
21     }
22     for(int i = 0; i < 6; i++)
23     {
24         ans *= C[num][t[i]];
25         num -= t[i];
26     }
27     return ans;
28 }
29 
30 int main()
31 {
32     //freopen("in.txt", "r", stdin);
33 
34     for(int i = 0; i <= maxn; i++) C[i][0] = C[i][i] = 1;
35     for(int i = 2; i <= maxn; i++)
36         for(int j = 1; j <= i; j++)
37             C[i][j] = C[i-1][j] + C[i-1][j-1];
38 
39     int T;
40     scanf("%d", &T);
41     while(T--)
42     {
43         memset(a, 0, sizeof(a));
44         int x;
45         for(int i = 0; i < 12; i++) { scanf("%d", &x); a[x-1]++; }
46         LL ans = 0;
47         ans += cal(1);  //原始排列
48         ans += 3 * cal(2);  //以两个对面的中心为轴旋转180°
49         ans += 3 * 2 * cal(4);  //以两个对面的中心为轴旋转90°或270°
50         ans += 4 * 2 * cal(3);  //以两个对角顶点为中心旋转
51         for(int i = 0; i < 6; i++)
52             for(int j = 0; j < 6; j++)
53             {//以两个对棱中心连线为轴旋转180°
54                 if(a[i] == 0 || a[j] == 0) continue;
55                 a[i]--; a[j]--;//减去两个1循环
56                 ans += 6 * cal(2);
57                 a[i]++; a[j]++;
58             }
59         printf("%lld\n", ans / 24);
60     }
61 
62     return 0;
63 }