Palindrome graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 96 Accepted Submission(s): 38
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?
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.
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
Source
Recommend
zhuyuanchen520
虽然说是水题，还是记录下。
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
#define ll __int64
using namespace std;
const ll mm=100000007;
ll a[10010];
int flag[2010];
int uu,n;
struct Node
{
int xx,yy,id;
}node[2000000];
int cmp(Node aa,Node bb)
{
if(aa.xx==bb.xx) return aa.yy<bb.yy;
return aa.xx<bb.xx;
}
void init()
{
a[1]=1;a[2]=1;
for(int i=3;i<=10000;i++)
a[i]=a[i-2]+(i+1)/2;
}
ll powermod(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1) res=(res*x)%mm;
y>>=1;
x=(x*x)%mm;
}
return res;
}
int find(int x)
{
if(flag[x]!=x) flag[x]=find(flag[x]);
return flag[x];
}
void solve(int pi,int pj,int i)
{
if(pi>=1&&pi<=n&&pj>=1&&pj<=n)
{
node[uu].xx=pi;node[uu].yy=pj;node[uu].id=i;uu++;
}
}
int main()
{
int m,k;
init();
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
if(m==0)
{
ll res=powermod(k,a[n]);
printf("%I64d\n",res);
continue;
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&node[i].xx,&node[i].yy);
node[i].xx++;
node[i].yy++;
node[i].id=i;
flag[i]=i;
}
uu=m;
for(int i=0;i<m;i++)
{
int pi,pj;
pi=node[i].yy;pj=node[i].xx;
solve(pi,pj,i);
pi=n-node[i].yy+1;pj=node[i].xx;
solve(pi,pj,i);
pi=node[i].xx;pj=n-node[i].yy+1;
solve(pi,pj,i);
pi=node[i].yy;pj=n-node[i].xx+1;
solve(pi,pj,i);
pi=n-node[i].yy+1;pj=n-node[i].xx+1;
solve(pi,pj,i);
pi=n-node[i].xx+1;pj=node[i].yy;
solve(pi,pj,i);
pi=n-node[i].xx+1;pj=n-node[i].yy+1;
solve(pi,pj,i);
}
sort(node,node+uu,cmp);
for(int i=1;i<uu;i++)
{
if(node[i].xx==node[i-1].xx&&node[i].yy==node[i-1].yy)
{
flag[find(node[i].id)]=find(node[i-1].id);
}
}
int count=0;
for(int i=0;i<m;i++)
{
if(find(i)==i) count++;
}
int bb=a[n]-count;
ll res=powermod(k,bb);
printf("%I64d\n",res);
}
}