UVA 10601 Cubes ( Burnside Lemma )

UVa Online Judge

題意：
給 12 條邊各自的顏色，顏色是 [ 1, 6 ] 間的整數，問可以組成多少種不同的立方體。旋轉後相同則視兩立方體相同。

資料規模：
The first line of input contains T (1 ≤ T ≤ 60), the number of test cases. Then T test cases follow. Each
test case consists of one line containing 12 integers. Each of them denotes the color of the corresponding
rod. The colors are numbers between 1 and 6.

解法：
用 Burnside Lemma，一共有 24 種不同的操作。
注意不能直接用 x / y / z 軸各自轉 [ 0, 4 ] 次去想，因為會有等價的操作。

( 第四種操作的圖裡，靠中間的循環圈方向有失誤畫反 )
歸類出 24 種操作分別的循環數量以及循環節長度，就能算出每個操作分別的等價 ( 操作後視為相同的 ) 組合數，對之求和後除以總操作數 ( 24 ) 即是答案。

時間 / 空間複雜度：
O( 6^2 )

#include <bits/stdc++.h>
using namespace std;

vector< int > cnt;

long long ways( int len ){
  vector< int > f = cnt;
  int s = 0;
  for( int i = 0; i < 6; ++i ){
    if( f[ i ] % len ) return 0;
    f[ i ] /= len;
    s += f[ i ];
  }
  long long res = 1;
  for( int i = 1; i <= s; ++i ){
    res *= i;
  }
  for( int i = 0; i < 6; ++i ){
    for( int j = 1; j <= f[ i ]; ++j ){
      res /= j;
    }
  }
  return res;
}

signed main(){
  ios::sync_with_stdio( 0 );
  int T; cin >> T;
  for( int ti = 0; ti < T; ++ti ){
    cnt = vector< int >( 6 );
    for( int i = 0; i < 12; ++i ){
      int c; cin >> c;
      ++cnt[ c - 1 ];
    }
    long long ans = 0;
    ans += ways( 1 ); // ways to split into groups of same color of length 1
    ans += 6LL * ways( 4 ); // x / y / z axis, 90 / 270
    ans += 3LL * ways( 2 ); // x / y / z axis, 180
    ans += 8LL * ways( 3 ); // point to point 4 axes, 120 / 240
    for( int i = 0; i < 6; ++i ){ // 6 axes, 5 * 2 + 2 * 1
      for( int j = 0; j < 6; ++j ){
        if( cnt[ i ] == 0 and cnt[ j ] == 0 ) continue;
        --cnt[ i ], --cnt[ j ];
        ans += 6LL * ways( 2 );
        ++cnt[ i ], ++cnt[ j ];
      }
    }
    cout << ans / 24 << "\n";
  }
  return 0;
}