|
题目链接：uva 10601 - Cubes
题目大意：有12根等长的小木棍，然后每根木棍，输入每根木棍颜色的编号，你的任务是统计出用它们拼出多少种不同的立方体，旋转之后完全相同的立方体被认定相同。
解题思路：polya，然后对应立方体有24种旋转：
- 不旋转（still）：1种，循环长度为12
- 以对顶点为轴（rot_point）：4组，循环长度为3
- 以对面中心为轴（rot_plane）：3组，分别有90，180，270度旋转，分别对应循环长度3，2，3
- 以对边为轴（rot_edge）：6组，除了两条边循环长度为1，其他为2.
#include
#include
#include
using namespace std; typedef long long ll; const int maxn = 12; int u[maxn+5], rod[maxn+5]; ll C[maxn+5][maxn+5]; void init () { memset(C, 0, sizeof(C)); for (int i = 0; i <= maxn; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) C[i][j] = C[i-1][j-1] + C[i-1][j]; } } ll solve (ll k) { int n = 0; ll ret = 1; for (int i = 0; i < 6; i++) { if (u[i] % k) return 0; u[i] /= k; n += u[i]; } for (int i = 0; i < 6; i++) { ret *= C[n][u[i]]; n -= u[i]; } //printf("%lld %lld!!\n", k, ret); return ret; } ll still () { memcpy(u, rod, sizeof(rod)); return solve(1); } ll rot_point () { memcpy(u, rod, sizeof(rod)); return 4 * 2 * solve(3); } ll rot_edge () { ll ret = 0; for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { if (rod[i] && rod[j]) { memcpy(u, rod, sizeof(rod)); u[i]--; u[j]--; ret += 6 * solve(2); } } } return ret; } ll rot_plane () { ll ret = 0; memcpy(u, rod, sizeof(rod)); ret += solve(4) * 2 * 3; memcpy(u, rod, sizeof(rod)); ret += solve(2) * 3; return ret; } inline ll polya () { return still() + rot_point() + rot_edge() + rot_plane(); } int main () { init(); int cas, x; scanf("%d", &cas); while (cas--) { memset(rod, 0, sizeof(rod)); for (int i = 0; i < maxn; i++) { scanf("%d", &x); rod[x-1]++; } printf("%lld\n", polya() / 24); } return 0; }
|