[Uva10601]Cubes

标签：置换 burnside引理

题意

给你12跟长度相同的小木棍，每个小木棍有一个颜色。统计他们能拼成多少种不同的立方体。旋转后相同的立方体认为是相同的。

题解

这道题难就难在他不告诉你正方体是怎么旋转的，所以只要把这个想清楚了这道题就不是很难。

有三种旋转方式：

以一个面与其对面的中心为轴旋转。这个可以旋转90,180,270度。

以一条棱与其对棱的中心为轴旋转。只能旋转180度。

以一个点与其对点的中心为轴旋转。能旋转120和240度。（其实就是以这个点为端点的边在旋转）

然后就可以弄一个6维背包来求了（虽然组合数也可以，但是6维背包难道不更爽一些吗？）

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define ll long long#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)inline int read(){ int sum=0,p=1;char ch=getchar(); while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar(); if(ch=='-')p=-1,ch=getchar(); while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar(); return sum*p;}int cnt[7];int dp[13][13][13][13][13][13];ll ans=0;void init(){ memset(cnt,0,sizeof(cnt)); REP(i,1,12)cnt[read()]++; ans=0;}int w[100],Cnt;void Dp(){ REP(a,0,cnt[1])REP(b,0,cnt[2])REP(c,0,cnt[3])REP(d,0,cnt[4])REP(e,0,cnt[5])REP(f,0,cnt[6])dp[a][b][c][d][e][f]=0; dp[0][0][0][0][0][0]=1; REP(l,1,Cnt) { DREP(a,cnt[1],0) { DREP(b,cnt[2],0) { DREP(c,cnt[3],0) { DREP(d,cnt[4],0) { DREP(e,cnt[5],0) { DREP(f,cnt[6],0) { if(a>=w[l])dp[a][b][c][d][e][f]+=dp[a-w[l]][b][c][d][e][f]; if(b>=w[l])dp[a][b][c][d][e][f]+=dp[a][b-w[l]][c][d][e][f]; if(c>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c-w[l]][d][e][f]; if(d>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c][d-w[l]][e][f]; if(e>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c][d][e-w[l]][f]; if(f>=w[l])dp[a][b][c][d][e][f]+=dp[a][b][c][d][e][f-w[l]]; } } } } } } }}void doing(){ Cnt=12; REP(i,1,12)w[i]=1; Dp(); ans+=dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]; Cnt=3; REP(i,1,3)w[i]=4; Dp(); ans+=6*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]; Cnt=6; REP(i,1,6)w[i]=2; Dp(); ans+=3*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]; Cnt=4; REP(i,1,4)w[i]=3; Dp(); ans+=8*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]; Cnt=7; w[1]=1;w[2]=1; REP(i,3,7)w[i]=2; Dp(); ans+=6*dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][cnt[6]]; cout<