题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1812

题解:

Burnside引理,Polya定理问题。

旋转只有 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

import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			BigInteger c = in.nextBigInteger();
			BigInteger ans = BigInteger.ZERO;
			if (n % 2 == 0) {
				ans = ans.add(c.pow(n*n));
				ans = ans.add(BigInteger.valueOf(2).multiply(c.pow(n*n/4)));
				ans = ans.add(BigInteger.valueOf(3).multiply(c.pow(n*n/2)));
				ans = ans.add(BigInteger.valueOf(2).multiply(c.pow((n*n - n)/2 + n)));
			} else {
				ans = ans.add(c.pow(n*n));
				ans = ans.add(BigInteger.valueOf(2).multiply(c.pow((n*n - 1)/4 + 1)));
				ans = ans.add(c.pow((n*n - 1)/2 + 1));
				ans = ans.add(BigInteger.valueOf(4).multiply(c.pow((n*n - n)/2 + n)));
			}
			ans = ans.divide(BigInteger.valueOf(8));
			System.out.println(ans);
		}
	}
}
转载保留版权:http://haipz.com/blog/i/5813 - 海胖博客