题面

话说就是因为这个游戏，Lele已经变成一个名人，每当他一出现在公共场合，就有无数人找他签名，挑战。

为了防止引起社会的骚动，Lele决定还是乖乖呆在家里。

在家很无聊，Lele可不想像其他人一样每天没事在家数钱玩，于是他就开始数棋盘。他想知道，一个有N×N个格子的正方形棋盘，每个格子可以用C种不同颜色来染色，一共可以得到多少种不同的棋盘。如果一个棋盘，经过任意旋转，反射后变成另一个棋盘，这两个棋盘就是属于同一种棋盘。

比如当N=C=2的时候，有下面六种不同的棋盘

现在告诉你N和C，请你帮帮Lele算算，到底有多少种不同的棋盘

本题目包含多组测试，请处理到文件结束。

每组测试数据包含两个正整数N和C(0<N,C,<31),分别表示棋盘的大小是N×N，用C种颜色来进行染色。

对于每组测试，在一行里输出答案。

2 2 3 1

6 1

题解

根据polya定理，

这道题的G中一共有8个元素，分别是①不动，②顺时针转90°，③转180°，④顺时针转270°，⑤左-右翻转，⑥上-下翻转，⑦左上-右下翻转，⑧左下-右上翻转。

C(i)就是每个元素的循环节个数，对于这道题可得：

实际的答案有可能达到N^2C级别，但是我们惊讶地发现这道题不取模，所以要用高精度

这道题很毒瘤，因为他的数据组数很大很大，每次直接算要超时，数据组数比31*31大得多，但是只有31*31种状态，所以我们记忆一下。

ＣＯＤＥ

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<iostream>
#define MAXN 100005
#define LL long long
#define ULL unsigned LL
#define rg register
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
//#pragma GCC optimize(2)
#define DB double
//#pragma G++ optimize(3)
#define int LL
using namespace std;
inline int read() {
    int f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
    while(s >= '0' && s <= '9') {x = x * 10 - '0' + s;s = getchar();}
    return x * f;
}
struct it{
    int len;
    LL s[3005];
    it(){len = 1;memset(s,0,sizeof(s));}
    it(int nm) {
        len = 1;memset(s,0,sizeof(s));
        for(int i = 1;nm;i ++) {
            s[i] = nm % 1000000000;
            nm /= 1000000000;
            if(s[i]) len = max(len,i);
        }
    }
    void print() {
        printf("%d",s[len]);
        for(int i = len-1;i > 0;i --) {
            printf("%09d",s[i]);
        }
    }
};
it operator + (it a,it b) {
    it c; LL m = 0;
    for(int i = 1;i <= a.len || i <= b.len || m;i ++) {
        c.s[i] = a.s[i] + b.s[i] + m;
        m = c.s[i] / 1000000000;
        c.s[i] %= 1000000000;
        if(c.s[i]) c.len = max(c.len,i);
    }
    return c;
}
it operator * (it a,it b) {
    it c; LL m = 0;
    for(int i = 1;i <= a.len;i ++) {
        m = 0;
        for(int j = 1;j <= b.len || m;j ++) {
            c.s[i + j - 1] += a.s[i] * b.s[j] + m;
            m = c.s[i+j-1] / 1000000000;
            c.s[i+j-1] %= 1000000000;
            if(c.s[i+j-1]) c.len = max(c.len,i+j-1);
        }
    }
    return c;
}
it operator / (it a,int b) {
    it c; LL m = 0;
    for(int i = a.len;i > 0;i --) {
        m = m * 1000000000 + a.s[i];
        c.s[i] = m / b;
        m %= b;
        if(c.s[i]) c.len = max(c.len,i);
    }
    return c;
}
int zxy;
LL n,m,i,j,s,o,k,ans;
LL gcd(LL a,LL b) {
    return b == 0 ? a : gcd(b,a % b);
}
LL qkpow(LL a,LL b) {
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a;
        b >>= 1; a = a * a;
    }
    return res;
}
it qkpow(it a,LL b) {
    it res(1);
    while(b) {
        if(b & 1) res = res * a;
        b >>= 1; a = a * a;
    }
    return res;
}
it dp[35][35];
bool vis[35][35];
signed main() {
    while(scanf("%d%d",&n,&m) == 2) {
        if(vis[n][m]) {
            dp[n][m].print();
            ENDL;
            continue;
        }
        it ans;
        it M(m);
        ans = (qkpow(M,n * n));
        ans = ans + (qkpow(M,(n & 1) ? ((n * n - 1) / 4 + 1) : (n * n / 4)) * it(2));
        ans = ans + (qkpow(M,(n & 1) ? ((n * n - 1) / 2 + 1) : (n * n / 2)));
        ans = ans + (qkpow(M,(n & 1) ? (n * (n+1) / 2) : (n * n / 2)) * it(2));
        ans = ans + (qkpow(M,n * (n+1) / 2) * it(2));
        ans = ans / 8;
        ans.print();
        dp[n][m] = ans;
        vis[n][m] = 1;
        ENDL;
    }
    return 0;
}