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
最後に、データ範囲に注意
タイトルリンク: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;
}