首页 > ACM题库 > HDU-杭电 > HDU 1812 Count the Tetris-高精度-[解题报告] java
2013
12-23

HDU 1812 Count the Tetris-高精度-[解题报告] java

Count the Tetris

问题描述 :

话说就是因为这个游戏,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

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

标准的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

AC代码:

import java.math.BigInteger;
import java.util.Scanner;


public class Main 
{
	static Scanner cin=new Scanner(System.in);
	public static void main(String[] args)
	{
		int n,t;
		BigInteger c,sum,x,two=BigInteger.valueOf(2),four,eight;
		four=BigInteger.valueOf(4);
		eight=BigInteger.valueOf(8);
		while(cin.hasNext())
		{
			n=cin.nextInt();
			c=cin.nextBigInteger();
			sum=BigInteger.ZERO;
			if(n%2==0)//偶数
			{
				x=c.pow(n*n);
				sum=sum.add(x);
				x=two.multiply(c.pow(n*n/4));
				sum=sum.add(x);
				x=c.pow(n*n/2);
				sum=sum.add(x);
				x=two.multiply(c.pow((n*n-n)/2+n));
				sum=sum.add(x);
				x=two.multiply(c.pow(n*n/2));
				sum=sum.add(x);
				sum=sum.divide(eight);
			}
			else
			{
				x=c.pow(n*n);
				sum=sum.add(x);
				x=two.multiply(c.pow((n*n-1)/4+1));
				sum=sum.add(x);
				x=c.pow((n*n-1)/2+1);
				sum=sum.add(x);
				x=four.multiply(c.pow((n*n+n)/2));
				sum=sum.add(x);
				sum=sum.divide(eight);
			}
			System.out.println(sum);
		}

	}

}

解题报告转自:http://blog.csdn.net/xh_reventon/article/details/9934257


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法