UVA 10601

发表于 |

题目

给$12$根相同长度的小棍，每个小棍的颜色是$1-6$中的一种。问可以构成多少种不同的正方体。旋转后相同算作同一种。

数据范围

null

做法

由于颜色个数有限制，所以不能用Polya定理，而要用Burnside引理。

正方体旋转有24种，有以下三类：绕过2个相对的面的中心的轴、绕体对称轴、绕过2个对棱中点的轴。

对每种置换，排列组合以下，计算其不动点的个数。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[7];
ll fact[13];
ll calc(int t)
{
  int s = 0;
  int tmp[7];
  memcpy(tmp, num, sizeof(num));
  for (int i = 1; i <= 6; ++i) {
    if (num[i] % t != 0) return 0;
    tmp[i] /= t;
    s += tmp[i];
  }
  ll res = fact[s];
  for (int i = 1; i <= 6; ++i) {
    res /= fact[tmp[i]];
  }
  return res;
}
void solve()
{
  ll res = 0;
  res += calc(1) + calc(4) * 6 + calc(2) * 3 + calc(3) * 8;
  for (int i = 1; i <= 6; ++i) {
    if (num[i] == 0) continue;
    num[i]--;
    for (int j = 1; j <= 6; ++j) {
      if (num[j] == 0) continue;
      num[j]--;
      res += 6 * calc(2);
      num[j]++;
    }
    num[i]++;
  }
  printf("%lld\n", res / 24);
}
int main()
{
  fact[0] = 1;
  for (int i = 1; i <= 12; ++i) {
    fact[i] = fact[i - 1] * i;
  }
  int T; scanf("%d", &T);
  while (T--) {
    memset(num, 0, sizeof num);
    for (int i = 0; i < 12; ++i) {
      int c; scanf("%d", &c);
      num[c]++;
    }
    solve();
  }
  return 0;
}