hdu4365 Palindrome graph

Palindrome graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2118 Accepted Submission(s): 664

Problem Description

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?

Input

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.

Output

For each case,print a integer in a line,indicate the number of ways jack can paint. The result can be very large, so print the result modulo 100 000 007.

Sample Input

3 0 2

4 2 3

1 1

3 1

Sample Output

8

3

题意：求出一个回文图的种类。给出了回文图的定义，即前后翻转或者旋转90度不改变图的样子。给你n，m，k分别表示有n*n的格子图，有m个格子已经涂上颜色，现在有k种颜色用来涂满剩余的格子，问有多少涂法。

解题思路：关键在于怎么将已经涂了色的点投影到同一个区域的。（因为图可以旋转翻转，我们发现是1/8的区域）。然后统计有多少个点已经上了色。剩下的点就是可以用k种颜色涂的了。由组合数学可做即求k的n次幂取1e+7的模

AC代码：

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define MOD 100000007
 4 using namespace std;
 5 //map < pair <int ,int > ,int > mp; 既可以用mp来找，也可以用数组。测试表明，map内存开销更小
 6 bool a[5050][5050]; //由于内存限制，数组开1/4大小就行
 7 int cnt=0;
 8 int quick_pow(int k,int x){
 9     long long ans=1,base=k;
10     while(x!=0){
11         if(x&1==1){
12             ans=(ans*base)%MOD;
13         }
14         base=(base*base)%MOD;
15         x>>=1;
16     }
17     return (int)ans%MOD;
18 }
19 void change(int x,int y,int n){ //投影到同一区域
20     if(x>n-1-x){
21         x=n-1-x;
22     }
23     if(y>n-1-y){
24         y=n-1-y;
25     }
26     if(x>y){    //翻转操作
27         swap(x,y);
28     }
29     if(a[x][y]==0){ 
30         cnt++;
31         a[x][y]=1;
32     }
33 }
34 int main(){
35     int n,m,k;
36     while(scanf("%d%d%d",&n,&m,&k)!=EOF){
37         cnt=0;
38         //mp.clear();
39         memset(a,0,sizeof(a));
40         while(m--){
41             int x,y;
42             scanf("%d%d",&x,&y);
43             change(x,y,n);
44         }
45         int sum=0;
46         if(n%2==0){
47             sum=((1+n/2)*(n/2))/2;
48         }else{
49             sum=((1+(n+1)/2)*((n+1)/2))/2;
50         }
51         cout<<quick_pow(k,sum-cnt)<<endl;
52     }
53     return 0;
54 }