题意简述：给你N和M，对于一个N∗M的单面方格纸你能够对它的每

个个格子黑白染色。然后把方格纸的长边卷起来，卷成一个圆柱体，然后再把

两个短边形成的圆也接起来。形成一个游泳圈的形状（我们染的色仅仅在游泳圈

的外表面）。假设对于两种黑白染色方案。通过卷成这种游泳圈后，是一样

的。则这两种方案也是一样的。给定N，M<=20。求染色方案总数.

分析：

首先我们得会Pólya定理，參见http://wenku.baidu.com/view/bf92a95f804d2b160b4ec0be.html

依据题目的要求，分两种情况：

①若N=M，那么就有翻转0o,90o,180o,270o与上下移动，左右移动共N∗M∗2∗2种置换；

②若N≠M，那么就有翻转0o,180o与上下移动，左右移动共N∗M∗2种置换；

依据Pólya定理，我们分三步：

①暴力搜出全部置换；

②搜出全部置换的循环。

③把答案累加后除以置换数。

时间复杂度：

①O(N∗M)②O(N∗M)

因此总的为O((N∗M)2)

ps.我们须要写高精度。能够预处理2的幂来进行加速。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 29;

const int MAXM = 29;

const int MAXL = 200;

int n, m;

int G;

bool check_square;

int ex[MAXN*MAXM];

struct bigNum

{

    int a[MAXL];

    bigNum(){memset(a, 0, sizeof(a));a[0] = 1;}

    inline void operator += (const bigNum &add)

    {

        a[0] = max(a[0], add.a[0]);

        for(int i = 1; i <= a[0]; ++i)

        {

            a[i] += add.a[i];

            a[i+1] += a[i]/10;

            a[i] %= 10;

        }

        if(a[a[0]+1]) a[0]++;

    }

    inline void operator /= (int k)

    {

        for(int i = a[0]; i > 0; --i)

        {

            a[i-1] += a[i]%k*10;

            a[i] /= k;

        }

        for(; a[0] > 0; --a[0])

            if(a[a[0]]) return ;

    }

    inline void print()

    {

        for(int i = a[0]; i > 0; --i)

            printf("%d", a[i]);

    }

}ans, pow2[MAXN*MAXM];

inline void init()

{

    scanf("%d%d", &n, &m);

    if(n == m) G = n*m*4, check_square = true;

    else G = n*m*2;

    for(int i = 1; i <= n*m; ++i)

        ex[i] = i;

}

inline int calc()

{

    int re = 0;

    bool hash[MAXN*MAXM] = {false};

    for(int i = 1; i <= n*m; ++i)

        if(!hash[i])

        {

            for(int j = i; !hash[j]; j = ex[j])

                hash[j] = true;

            re++;

        }

    return re;

}

inline void rotate()

{

    int nex[MAXN*MAXM] = {0};

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j)

            nex[(m-j)*n+i] = ex[(i-1)*m+j];

    for(int i = 1; i <= n*m; ++i) ex[i] = nex[i];

    swap(n, m);

}

inline void shift_down()

{

    int nex[MAXN*MAXM] = {0};

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j)

            nex[(i%n)*m+j] = ex[(i-1)*m+j];

    for(int i = 1; i <= n*m; ++i) ex[i] = nex[i];

}

inline void shift_right()

{

    int nex[MAXN*MAXM] = {0};

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= m; ++j)

            nex[(i-1)*m+j%m+1] = ex[(i-1)*m+j];

    for(int i = 1; i <= n*m; ++i) ex[i] = nex[i];

}

inline void work()

{

    pow2[0].a[0] = pow2[0].a[1] = 1;

    for(int i = 1; i <= n*m; ++i)

    {

        bigNum tmp = pow2[i-1];

        tmp += pow2[i-1];

        pow2[i] = tmp;

    }

    for(int i = 1; i <= n; ++i)

    {

        for(int j = 1; j <= m; ++j)

        {

            ans += pow2[calc()];

            rotate();

            if(check_square) ans += pow2[calc()];

            rotate();

            ans += pow2[calc()];

            rotate();

            if(check_square) ans += pow2[calc()];

            rotate();

            shift_right();

        }

        shift_down();

    }

    ans /= G;

}

inline void print()

{

    ans.print();

    puts("");

}

int main()

{

    init();

    work();

    print();

    return 0;

}