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
      
        2 #include
       
         3 #define MOD 100000007 4 using namespace std; 5 //map < pair 
        
          ,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<
         
          <