首页 > ACM题库 > HDU-杭电 > HDU 4365-Palindrome graph-模拟-[解题报告]HOJ
2015
05-23

HDU 4365-Palindrome graph-模拟-[解题报告]HOJ

Palindrome graph

问题描述 :

In addition fond of programing, Jack also loves painting. He likes to draw many interesting graphics on the paper.
One day,Jack found a new interesting graph called Palindrome graph. No matter how many times to flip or rotate 90 degrees, the palindrome graph are always unchanged.
Jack took a paper with n*n grid and K kinds of pigments.Some of the grid has been filled with color and can not be modified.Jack want to know:how many ways can he paint a palindrome graph?

输入:

There are several test cases.
For each test case,there are three integer n m k(0<n<=10000,0<=m<=2000,0<k<=1000000), indicate n*n grid and k kinds of pigments.
Then follow m lines,for each line,there are 2 integer i,j.indicated that grid(i,j) (0<=i,j<n) has been filled with color.
You can suppose that jack have at least one way to paint a palindrome graph.

输出:

There are several test cases.
For each test case,there are three integer n m k(0<n<=10000,0<=m<=2000,0<k<=1000000), indicate n*n grid and k kinds of pigments.
Then follow m lines,for each line,there are 2 integer i,j.indicated that grid(i,j) (0<=i,j<n) has been filled with color.
You can suppose that jack have at least one way to paint a palindrome graph.

样例输入:

3 0 2
4 2 3
1 1
3 1

样例输出:

8
3

九野的博客,转载请注明出处:

http://blog.csdn.net/acmmmm/article/details/10195947

题意:求用k种颜料将n*n大的方格涂满的方法有多少种,这里已经有m个格子上过色了

涂满后的方格要满足:中心对称,翻转对称,旋转对称

 

思路:

1、从对称可以得到 方格可以分为对称的8瓣 所以我们用2条对角线和 2条中位线 把方格切成八瓣,每一瓣的方格数有 0 + 1 + 2 + …… + [n+1]/2  (方格数计算是包含分割线上的方格)

2、若不考虑已上过色的格子 方案就是 k^ (每一瓣的方格数)

3、把上过色的方格都投影到第一瓣方格中(注意存在对称同色的方格),则答案是 k^ ( 投影后剩下的方格数)

4、k较大,需要用快速幂计算

 

#include<stdio.h>
#include<string.h>
#define ll __int64
#define f(x) (x*(x+1))/2
#define MOD 100000007
ll quickpow(ll m,ll n)
{
	ll b = 1;
	while (n)
	{
		if (n&(ll)1)
			b = (b*m)%MOD;
		n >>=(ll)1;
		m = (m*m)%MOD;
	}
	return b;
} 
ll k;
int n,m;
bool map[5050][5050];

void PUT(int x){
	for(int i=1;i<=x;i++){

		for(int j=1;j<=x;j++)
			printf("%d ",map[i][j]);
		printf("\n");
	}
	printf("\n");
}

int Is(int x,int y){
	int mid;
	if(n&1)
	{
		mid=(1+n)>>1;
		if(x>mid)x-=2*(mid-x);
		if(y>mid)y-=2*(mid-y);
	}
	else 
	{
		mid=n>>1;
		if(x>mid)x=2*mid+1-x;
		if(y>mid)y=2*mid+1-y;
	}
	if(map[x][y])return 0;
	return map[x][y]=map[y][x]=1;
}
int main(){
	int u,v;
	while(~scanf("%d %d %I64d",&n,&m,&k)){
		int num=0,z=n>>1;
		for(int i=1;i<=z;i++)
			for(int j=1;j<=z;j++)
				map[i][j]=0;
		while(m--)
		{
			scanf("%d%d",&u,&v);
			num+=Is(1+u,1+v);
		}

		//		PUT(n);
		n=(n+1)/2;
		n=f(n)-num;
		ll ans=quickpow(k,n);
		printf("%I64d\n",ans);
	}
	return 0;
}
/*
3 0 2
4 2 3
1 1
3 1

5 3 999
0 0
0 1
0 2

*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acmmmm/article/details/10195947