【UVa10601】Cubes-Burnside引理应用

测试地址：Cubes
题目大意：给你12根长度相同的棒子，每根棒子都有颜色，颜色不超过6种，问可以组成的本质不同的立方体的数量。我们说两个立方体本质不同，当且仅当如何旋转它们都不能使它们的着色方案重合。
做法：这一题需要使用Burnside引理来解决。
首先介绍Burnside引理：设G是一个置换群，C(f)是经过置换f后和原来相同的所有着色方案形成的集合，那么不等价的着色方案数为：

1|G|∑f∈G|C(f)|

我们知道对于某一个置换f，里面肯定会有循环，要求|C(f)|，实际上就是求在置换f的同一个循环内着色相同的着色方案数，这时如果没有任何限制，设颜色种数为M，循环数为c(f)，那么|C(f)|=Mc(f)，代入上式就成了Polya定理，所以Polya定理是Burnside引理的一个特殊情况。
回到这一题里，我们要考虑两个难点：1.如何求出置换群；2.如何求出每个置换的|C(f)|。下面我们就来一一探讨这两个问题。
要求出符合本题要求的置换群，就要搞清楚立方体有什么不同的旋转方式。综合来看可以分为以下四种：
第一种是静止不动，这样只有一种情况，置换的循环数是12，每个循环节长度为1；
第二种是以一条对角线为轴旋转，立方体有4条这样的对角线，这时候有两种情况：转120∘和转240∘，每种情况循环数都是4，每个循环节长度为3；
第三种是以一对相对的棱的中点连线为轴旋转，立方体有6条这样的轴，这种时候只有一种情况：转180∘，这时候置换有7个循环，其中有两个循环节长度为1，其他循环节长度为2；
第四种是以一对相对的面的中点连线为轴旋转，立方体有3条这样的轴，这时候有三种情况：转90∘，转180∘和转270∘，其中转90∘和转270∘的情况下，置换有3个循环，每个循环节长度为4，而对于转180∘的情况，置换有6个循环，每个循环节长度为2。
综上所述，我们要求的置换群G共有24种不同的置换，有一定空间想象能力的同学应该不难理解，实在不理解我也没办法了，自己拿个盒子比划比划吧……
然后第二个问题，就是怎么求各个置换的|C(f)|。由于题目要求必须用这12根棒构成立方体，这就间接限制了每种颜色的棍棒数，因此我们不能使用Polya定理。我们首先考虑每个循环节长度相同的情况，我们发现这样一个规律：设循环数为p，每个循环节长度为q，因为棒子要用完，如果某个颜色的木棒数不能整除q，那么就没有合法的着色方案，否则可以将所有棒子分成p组，每组颜色相同，那么每种着色方案就对应着这p组棒子的一个排列，带重元素的排列数公式我们是知道的（不知道的去查吧），那么我们直接套用公式就可以求出|C(f)|了。再回去看上面的各种情况，发现大部分情况都可以用这个方法计算，只有一种情况不同——第三种，那么我们可以先枚举那两个长度为1的循环里填的是什么颜色，然后剩下的再使用公式计算。这样我们就完美解决了这一道题。
以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll T,c[10],ans,fac[20];

ll solve(int p,int q)
{
  ll s=1;
  for(int i=1;i<=6;i++)
    if (c[i]%q!=0) return 0;
  for(int i=1;i<=6;i++)
    s*=fac[c[i]/q];
  return fac[p]/s;
}

void solve_still()
{
  ans+=1*solve(12,1);
}

void solve_plane()
{
  ans+=3*2*solve(3,4)+3*1*solve(6,2);
}

void solve_edge()
{
  for(int i=1;i<=6;i++)
    if (c[i]>0)
    {
      c[i]--;
      for(int j=1;j<=6;j++)
        if (c[j]>0)
        { 
          c[j]--;
          ans+=6*1*solve(5,2);
          c[j]++;
        }
      c[i]++;
    }
}

void solve_point()
{
  ans+=4*2*solve(4,3);
}

int main()
{
  scanf("%lld",&T);
  fac[0]=1;
  for(int i=1;i<=12;i++)
    fac[i]=fac[i-1]*i;
  while(T--)
  {
    ans=0;
    memset(c,0,sizeof(c));
    for(int i=1,x;i<=12;i++)
    {
      scanf("%d",&x);
      c[x]++;
    }
    solve_still();
    solve_plane();
    solve_edge();
    solve_point();
    printf("%lld
",ans/24);
  }

  return 0;
}