题目是一个有限制的正方体棱的填色。

与其说是Pólya定理的题目,不如说是置换群的题目。

参考cxlove菊苣的题解才搞懂。。。

正方体有24种置换。

+静止不动
+体对角线上对立的顶点
+相对面的中心
+相对的楞中心连线

根据Burnside定理,本质不同的方案数为在每个置换下稳定不动的方案数处以总置换数。

而要得到置换下稳定不动的方案,即把置换的每个循环节染上想上相同的颜色。

###Code

UVA 10601
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
#define LL long long
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

int t, tmp;
int c[15][15];
int a[10], b[10];
long long ans = 0;

LL make(int k) {
int n = 0;
LL sum = 1;
for(int i = 0; i < 6; i ++) {
if(b[i] % k == 0) {
b[i] /= k;
n += b[i];
}
else
return 0;
}
for(int i = 0; i < 6; i ++) {
sum *= c[n][b[i]];
n -= b[i];
}
return sum;
}

void init() {
for(int i = 0; i <= 13; i ++) {
c[i][0] = c[i][i] = 1;
for(int j = 1; j < i; j ++) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}

void solve() {
//静止不动
memcpy(b, a, sizeof(a));
ans += make(1);
//体对角线上对立的顶点
memcpy(b, a, sizeof(a));
ans += 4 * 2 * make(3);
//相对面的中心
memcpy(b, a, sizeof(a));
ans += 3 * 2 * make(4); //旋转90和270度
memcpy(b, a, sizeof(a)); //旋转180度
ans += 3 * make(2);
//相对的楞中心连线
for(int i = 0; i < 6; i ++)
for(int j = 0; j < 6; j ++) {
memcpy(b, a, sizeof(a));
b[i] --;
b[j] --;
if(b[i] < 0 || b[j] < 0) continue;
ans += 6 * make(2);
}
ans /= 24;
}

int main() {
memset(c, 0, sizeof(c));
init();
scanf("%d", &t);
while(t --) {
ans = 0;
memset(a, 0, sizeof(a));
for(int i = 0; i < 12; i ++) {
scanf("%d", &tmp);
a[tmp - 1] ++;
}
solve();
printf("%lld\n", ans);
}
return 0;
}