題目大意：給定一張有n*m個格子的紙，每個格子有黑白兩種顏色可以染。現在先將紙按長邊粘起來得到一個圓柱，再將紙按短邊拈起來得到一個游泳圈。如果兩種染色方案卷起來後是一樣的，那麼它們同構。問不同構的的染色方案。n,m <= 20.www.2cto.com
解題思路：Polya的核心是找置換，本題有兩類置換，一類是滾動，一類是旋轉。
我們將n*m的紙想成一個矩陣，那麼第一行是1,2,3...m,第二行是m+1...m*2，以此類推。
第一類滾動置換有n*m個。行和列是分開的，行的滾動有n個，列的滾動有m個，它們相乘就是總置換數。每個置換的循環節個數我們就模擬下，O（n*m）找到循環節。
第二類旋轉置換要分類討論，當n！= m時，我們可以將整個矩陣旋轉180度，這裡是旋轉而不是翻轉，我寫了Rorate函數將矩陣旋轉九十度，Rorate兩次.當n==m時，不僅可以旋轉180度，旋轉90度和270度都要考慮在內。
也就是說當n！=m時，置換有2*n*m個，當n==m時，置換有4*n*m個，再套個高精度模板就AC了。n和m很小，隨便模擬。
ac後我很ws地把結果打成表拿去提交，時間就是0s...
高精度模板太長，我就不發上來了，百度下一坨。
測試數據：
[cpp]
"2","3","4","6","8","13","18","30","46","78","126","224",
"380","687","1224","2250","4112","7685","14310","27012",
"3","6","13","34","78","237","687","2299","7685","27190","96909","353384","1296858",
"4808707","17920860","67169299","252745368","954677597","3617214681","13744852240",
"4","13","28","224","1224","7696","50964","352698","2493784","17920860","130216124",
"954637904","7048675960","52359294790","390941664896","2932043766538","22076502318624",
"166800088124428","1264168584899532","9607680019329456",
"6","34","224","1171","27012","353384","4806078","67169332","954637558","13744852240",
"199914398490","2932046213652","43303893547956","643371617410504","9607680019329456",
"144115191934621732","2170205198153526576","32794211748156196824","497091208931087393202","7555786373574120939544",
"8","78","1224","27012","337664","17920860","490984488","13744694928","390941662712",
"11259024570048","327534652572024","9607680019329456","283796066967422192","8432797316853883164",
"251859545890487150848","7555786373422938025200","227562507225975302929472","6877444662723140842510068",
"208495164511362678524008344","6338253001141997061913643712",
"13","237","7696","353384","17920860","477339616","52359294790","2932046213314","166800088124428",
"9607680171442372","558992251165454994","32794211748156896384","1937381121593132140708","115135792348177228029522",
"6877444662723140878302528","412646679762044113662598674","24855894122123845015649413488","1502400711381621229389905570832",
"91092927342716382903223175969098","5538449982437150493650373937210144",
"18","687","50964","4806078","490984488","52359294790","2872202032640","643371579062292","73201367519380268","8432797316853883164",
"981270957754284704684","115135792347575114543648","13603736695478923656694872","1616901275801738096771851776","193165805749068031447071325904",
"23179896689887677706535219983812","2792495789464109553149422598133408","337581713215216736580493443081144242","40936224591992597182162868918208830204",
"4977844910386299809268168657185593495464",
"30","2299","352698","67169332","13744694928","2932046213314","643371579062292","72057595967392816","32794211738611821312",
"7555786373574120887164","1758437555816391076574364","412646679762044113663297912","97511584632944122543696551480",
"23179896689887687357105852460494","5538449982437150339927506647332280","1329227995784915889260880907091324992","320265757102059730540916250236523351840",
"77433143050453552578958061549803284618034","18779574904025787908718574436155314063657516","4567192616659071619387584246010106165386598032",
"46","7685","2493784","954637558","390941662712","166800088124428","73201367519380268","32794211738611821312","7462505059899322983424","6877444662723140842510068",
"3201137879364778610385398532","1502400711381618810790106910044","710057690056045092131987186099464","337581713215216736580493443081144242",
"161319048021778234678358952710942506464","77433143050453552578334971527757506752592","37313665168783264864344472097714361025020896",
"18043230090504974298812744711929778187809121280","8751916237583886480939063648792742032126941483252","4256932057960802384328742673977943978507520207880680",
"78","27190","17920860","13744852240","11259024570048","9607680171442372","8432797316853883164","7555786373574120887164","6877444662723140842510068","3169126500571074529242309120",
"5900337339244149490513314759636","5538449982437150493650373937210144","5235113337245207158017777333159559848","4977844910386299809424175407065863134364","4757492309019866270222746693509250935268480",
"4567192616659071619387584246010106137898781148","4401699048902484083060538741828788515205714226528","4256932057960802384328742835597893551876416196246244","4129672194333342607786703597714589062014181942348177028","4017345110647475688854905231971608161006919942602792622080",
"126","96909","130216124","199914398490","327534652572024","558992251165454994","981270957754284704684","1758437555816391076574364","3201137879364778610385398532","5900337339244149490513314759636","5492677668532710795071526353530880","20623173752784149356430310745388844192",
"38987316780647942557493557843966923142152","74142737283426487327816994675197228663038210","141721370892693616310665183118190969688269247088","272105032113971743316468100029607746115481794298284","524490452488860357940824660906834687286247032453695456",
"1014481088547342345670430614328713611274506321265944117462","1968306886747854117410250218390318898817450552760765269658228","3829537878856624970833382824861719499244012007716179105915972728",
"224","353384","954637904","2932046213652","9607680019329456","32794211748156896384","115135792347575114543648","412646679762044113663297912","1502400711381618810790106910044","5538449982437150493650373937210144",
"20623173752784149356430310745388844192","38716571525226776289479030777920527620096","292768757478145616627568353963714924651956544","1113525057014021271012348398782331565126603893264","4256932057960802384328742673977943997722878635874368",
"16346619102569481155822368359546910178319955089970347032","63017178206234912766351454605429599454500254671266249005824","243778452936474969208143582601375171036664337413095870136407904","945963040952654027883053160948072839055886448893139296538105286176","3680931384954967353298536459881081412689429403953023045640442730653712",
"380","1296858","7048675960","43303893547956","283796066967422192","1937381121593132140708","13603736695478923656694872","97511584632944122543696551480","710057690056045092131987186099464","5235113337245207158017777333159559848","38987316780647942557493557843966923142152","292768757478145616627568353963714924651956544",
"1106936151351216411420552029913564178922327982080","16840610339185591850091727436792247974899305312795012","128761061238701143873554654993485379717996958608129280224","988884950313224784948899749148283703008718603990619363013720","7624419306320882294871893406963863309971744686132407647018850240","58989285015303963995168853523735385247513355610223113029848640459820",
"457806526906140069203769392905047723236896716886774810436054850189035496",
"3562833514994344474571414923344243319585618031758839964400217375270363818736",
"687","4808707","52359294790","643371617410504","8432797316853883164","115135792348177228029522","1616901275801738096771851776","23179896689887687357105852460494","337581713215216736580493443081144242","4977844910386299809424175407065863134364","74142737283426487327816994675197228663038210","1113525057014021271012348398782331565126603893264","16840610339185591850091727436792247974899305312795012",
"128104117048707770690526314899202091297678676061041606656","3917867993621919147988021863262307113933919244106603877001624",
"60178452382032678113096015819244825068964878748781540753477059454","927965895366798492428202468877583753967819789325306700235011436103152","14359138050262425027724576513974194997223644384576871790727992302294929122","222878006351525909988226858362587251214481350740984868249503310148931066031610","3469051593260230483784753405041998047576953537077802225138144613894348183375390368",
"1224","17920860","390941664896","9607680019329456","251859545890487150848","6877444662723140878302528","193165805749068031447071325904","5538449982437150339927506647332280","161319048021778234678358952710942506464","4757492309019866270222746693509250935268480","141721370892693616310665183118190969688269247088","4256932057960802384328742673977943997722878635874368","128761061238701143873554654993485379717996958608129280224",
"3917867993621919147988021863262307113933919244106603877001624","59910992593668088432593366860046219867622922022011434742524149760",
"3680931384954967353298536459881081240997479948401389438212823611161080","113521656115015877866246063734007752967464697838548367792434865181419404416","3513217759378126936703309293300634596825294857048152483694922263592674323175024","109062113247760228542846984242723868443088064396244307533219112480725667221801975984","3395059960557476810447409480682296935085781728924409435040082236571049272467566764776576",
"2250","67169299","2932043766538","144115191934621732","7555786373422938025200","412646679762044113662598674","23179896689887677706535219983812","1329227995784915889260880907091324992","77433143050453552578334971527757506752592","4567192616659071619387584246010106137898781148","272105032113971743316468100029607746115481794298284",
"16346619102569481155822368359546910178319955089970347032","988884950313224784948899749148283703008718603990619363013720","60178452382032678113096015819244825068964878748781540753477059454","3680931384954967353298536459881081240997479948401389438212823611161080","113078212145816597093331040047546785162829425924788878012961645803788578816","13949541103413151072204316311634872663800607794105716812074194835909818291033760",
"863408396544768475964205291921563958507756002213825299421102763621947441020673788034","53606209903539107533380149694983635817143909387604872165580443691146388265818995945327356","3337479743626422003742221415889925179066725817467934674631781173079522345479830488216782508880",
"4112","252745368","22076502318624","2170205198153526576","227562507225975302929472","24855894122123845015649413488","2792495789464109553149422598133408","320265757102059730540916250236523351840","37313665168783264864344472097714361025020896","4401699048902484083060538741828788515205714226528","524490452488860357940824660906834687286247032453695456","63017178206234912766351454605429599454500254671266249005824",
"7624419306320882294871893406963863309971744686132407647018850240","927965895366798492428202468877583753967819789325306700235011436103152","113521656115015877866246063734007752967464697838548367792434865181419404416","13949541103413151072204316311634872663800607794105716812074194835909818291033760","860420824238385194040453716516991072838170580817837530779501528452020967971736256512",
"213023370074194623400621771336928435142637226220410832023930328748982961739927069870232400","26451851838029846221610175927796311016751758793717464821993590453400802802034925791918206736480","3293742267908535603760944530247712173708302201816785714842272674335857064883154074899884841486918720",
"7685","954677597","166800088124428","32794211748156196824","6877444662723140842510068","1502400711381621229389905570832","337581713215216736580493443081144242","77433143050453552578958061549803284618034","18043230090504974298812744711929778187809121280","4256932057960802384328742835597893551876416196246244","1014481088547342345670430614328713611274506321265944117462",
"243778452936474969208143582601375171036664337413095870136407904","58989285015303963995168853523735385247513355610223113029848640459820","14359138050262425027724576513974194997223644384576871790727992302294929122","3513217759378126936703309293300634596825294857048152483694922263592674323175024","863408396544768475964205291921563958507756002213825299421102763621947441020673788034",
"213023370074194623400621771336928435142637226220410832023930328748982961739927069870232400","26370210320011235585123724767525334748181537315616256213169077454672893038017317811108955160576","13097922468876048014955802810341779404220149106637626639549018713584678848561019262022944004246153342","3261864698296990594290945273318523649132892429039334501079122693944244956398239758515309761637828058447328",
"14310","3617214681","1264168584899532","497091208931087393202","208495164511362678524008344","91092927342716382903223175969098","40936224591992597182162868918208830204","18779574904025787908718574436155314063657516","8751916237583886480939063648792742032126941483252","4129672194333342607786703597714589062014181942348177028","1968306886747854117410250218390318898817450552760765269658228","945963040952654027883053160948072839055886448893139296538105286176","457806526906140069203769392905047723236896716886774810436054850189035496","222878006351525909988226858362587251214481350740984868249503310148931066031610","109062113247760228542846984242723868443088064396244307533219112480725667221801975984","53606209903539107533380149694983635817143909387604872165580443691146388265818995945327356","26451851838029846221610175927796311016751758793717464821993590453400802802034925791918206736480","13097922468876048014955802810341779404220149106637626639549018713584678848561019262022944004246153342","3252829062013619429209806920760854608553576937546150171659530781326990155786545898224408100822922837360640","3240296562203493356272947376656547187917741716321171602161611329594481960205440267600480592491663403276323090072",
"27012","13744852240","9607680019329456","7555786373574120939544","6338253001141997061913643712","5538449982437150493650373937210144",
"4977844910386299809268168657185593495464","4567192616659071619387584246010106165386598032","4256932057960802384328742673977943978507520207880680","4017345110647475688854905231971608161006919942602792622080",
"3829537878856624970833382824861719499244012007716179105915972728","3680931384954967353298536459881081412689429403953023045640442730653712","3562833514994344474571414923344243319585618031758839964400217375270363818736",
"3469051593260230483784753405041998047576953537077802225138144613894348183375390368","3395059960557476810447409480682296935085781728924409435040082236571049272467566764776576",
"3337479743626422003742221415889925179066725817467934674631781173079522345479830488216782508880","3293742267908535603760944530247712173708302201816785714842272674335857064883154074899884841486918720",
"3261864698296990594290945273318523649132892429039334501079122693944244956398239758515309761637828058447328","3240296562203493356272947376656547187917741716321171602161611329594481960205440267600480592491663403276323090072",
"1613906173804317868534949482501882421456066120518264695519868146241101057612841996237852338189217258473599448105091072"
C艹代碼：
[cpp]
int n,m,arr[MAX][MAX],vis[MAX][MAX];
int cnt[MAX*MAX],temp[MAX][MAX];
int Calculate(int arr[][MAX]) {
int i,j,k,tp,ii,jj,tot = 0;
memset(vis,0,sizeof(vis));
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
if (vis[i][j] == 0) {
tot++;
ii = i,jj = j;
// printf("tot = %d\n",tot);
while (1) {
vis[ii][jj] = 1;
tp = arr[ii][jj];
//printf("ii%d jj%d tp%d\n",ii,jj,tp);
ii = (tp + m - 1) / m;
jj = tp - (ii - 1) * m;
if (vis[ii][jj]) break;
}
}
return tot;
}
void UpMove(int arr[][MAX]) {
memcpy(arr[n+1],arr[1],sizeof(arr[1]));
for (int i = 2; i <= n; ++i)
memcpy(arr[i-1],arr[i],sizeof(arr[i]));
memcpy(arr[n],arr[n+1],sizeof(arr[n+1]));
}
void LeftMove(int arr[][MAX]) {
int i,j,k;
for (i = 1; i <= n; ++i)
arr[i][m+1] = arr[i][1];
for (j = 2; j <= m; ++j)
for (i = 1; i <= n; ++i)
arr[i][j-1] = arr[i][j];
for (i = 1; i <= n; ++i)
arr[i][m] = arr[i][1+m];
}
void Rotate(int arr[][MAX]) {
int i,j,k,brr[MAX][MAX];
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
brr[j][n+1-i] = arr[i][j];
memcpy(arr,brr,sizeof(brr));
k = n,n = m, m = k;
}
void Print(int arr[][MAX]) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
printf("%d%c",arr[i][j],j==m?'\n':' ');
}
BigNum Power(int n,int k) {
BigNum x = n,ans = 1;
while (k) {
if (k & 1) ans = x * ans;
x = x * x,k >>= 1;
}
return ans;
}
int main()
{
int i,j,k,ii,jj,tp;
while (scanf("%d%d",&n,&m) != EOF) {
if (n > m) k = n,n = m,m = k;
memset(arr,0,sizeof(arr));
memset(cnt,0,sizeof(cnt));
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
arr[i][j] = j + (i - 1) * m;
for (ii = 1; ii <= n; ++ii) {
memcpy(temp,arr,sizeof(arr));
for (jj = 1; jj <= m; ++jj) {
tp = Calculate(temp); //0度
cnt[tp]++;
Rotate(temp); //90度
if (n == m)
tp = Calculate(temp),cnt[tp]++;
Rotate(temp); //180度
tp = Calculate(temp);
cnt[tp]++;
Rotate(temp); //270度
if (n == m)
tp = Calculate(temp),cnt[tp]++;
Rotate(temp); //360度
LeftMove(temp);
}
UpMove(arr);
}
BigNum ans = 0;
for (i = 1; i <= n * m; ++i)
if (cnt[i]) ans = ans + Power(2,i) * cnt[i];
if (n != m) ans = ans / (2 * n * m);
else ans = ans / (4 * n * m);
ans.print();
}
}
