高精度+polya原理可以搞定
思路：
设边长为n的正方形，c种颜色。
旋转只有 0，90，180，270度三种旋法。
旋0度，则置换的轮换数为n*n
旋90度，n为偶数时，则置换的轮换数为n*n/4，n为奇数，则置换的轮换数为(n*n-1)/4+1
旋180度，n为偶数时，则置换的轮换数为n*n/2，n为奇数，则置换的轮换数为(n*n-1)/2+1
旋270度，n为偶数时，则置换的轮换数为n*n/4，n为奇数，则置换的轮换数为(n*n-1)/4+1
反射 沿对角反射两种，沿对边中点连线反射两种
n为偶数时，沿对边中点连线反射两种的置换轮换数为 n*n/2
沿对角反射两种的置换轮换数为 (n*n-n)/2+n
n为奇数时，沿对边中点连线反射两种的置换轮换数为 (n*n-n)/2+n
沿对角反射两种的置换轮换数为 (n*n-n)/2+n
综上所述：用m种颜色给n*n矩形染色的方案数L
S=m^(n*n)+m^((n*n+3)/4)+m^((n*n+1)/2)+m^((n*n+3)/4) （考虑旋转时）
n为奇数L= (S+4*m^((n*n+n)/2)) / 8
n为偶数L= (S+2*m^((n*n+n)/2)+2*m(n*n/2) )/ 8……
这个用Java写的很方便
import java.io.*; import java.util.*;
import java.math.*;
public class Main
{
public static void main(String args[]) throws Exception
{
Scanner cin=new Scanner(System.in);
int n,s1,s2,s;
BigInteger c;
BigInteger two = new BigInteger("2");
BigInteger eight = new BigInteger("8");
BigInteger four = new BigInteger("4");
BigInteger sum;
while(cin.hasNext())
{
n=cin.nextInt();
c=cin.nextBigInteger();
if(n%2!=0)
{
s1=(n*n-1)/4+1;
s2=(n*n-1)/2+1;
}
else
{
s1=n*n/4;
s2=n*n/2;
}
sum=c.pow(s2);
sum=sum.add(c.pow(s1).multiply(two));
sum=sum.add(c.pow(n*n));
if(n%2!=0)
{
s=(n*n+n)/2;
sum=sum.add(c.pow(s).multiply(four));
}
else
{
s=(n*n+n)/2;
sum=sum.add(c.pow(s2).multiply(two));
sum=sum.add(c.pow(s).multiply(two));
}
sum=sum.divide(eight);
System.out.println(sum.toString());
}
}
}