2015
05-23

# 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

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

*/