Hoj 2084 The Colored Cubes(polyaカウント)

1008 ワード

最初の道 polyaカウントの問題、最も基礎的な入門問題.
タイトルリンク:http://acm.hit.edu.cn/hoj/problem/view?id=2084
标题:n種の色で正六面体を染色し、何種の異なる状況があるかを求める.
考え方:
(1)図の中心対称軸を見つけます.本題は3種類あります:面と面の中心、稜と稜の中心、対称の頂点.
(2)不動置換を書き出します.回転角度が0であれば不動置換であり、不動置換は一度しか計算できないため、以下の対称軸の置換はいずれも0度を考慮しない場合がある.
本題不動置換1個、循環節6
(3)異なる中心対称軸に沿って回転する置換を書く.
面と面の中心の置き換え
回転90度:3種類、各サイクルセグメントは3個(1,1,4)
回転180度:3種類、各サイクルセグメントは4個(1,1,2,2)
270度回転:同90度
稜と稜の中心置換:6種(12本の稜は合わせて6対・・)で、各サイクル節が3個(各稜は2面共用なので1回回転して同構造になる)
頂点と頂点の置換:4*2種(8個の頂点は4対で、1対120度と240度に分かれている)、各2サイクル(3,3)
(4)式により推定された結果は (n^6+3n^4+12n^3+8n^2)/24
最後に、データ範囲に注意
#include 

long long Cal (long long a,int index) // 
{
    long long ans=1;
    while (index--)
        ans*=a;
    return ans;
}

int main ()
{
    long long n,ans;
    while (scanf("%lld",&n),n)
    {
        ans=Cal(n,6)+3*Cal(n,4)+12*Cal(n,3)+8*Cal(n,2);
        ans/=24;
        printf("%lld
",ans); } return 0; }