HDU 4365Palindrome graph(找规律快速幂取模)

Palindrome graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1306 Accepted Submission(s): 398

Problem Description

In addition fond of programing, Jack also loves painting. He likes to draw many interesting graphics on the 易做图.

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 易做图 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

Author

FZU

Source

2012 Multi-University Training Contest 7

题目大意：flip是翻转的意思，rotate是旋转的意思。就是说给你一个n*n的格子，然后每个格子图上任意颜色，但是通过翻转旋转必须一样。高度轴对称和中心对称。

解题思路：经过思考可以发现，我们将正方形先等分成四份，如果一份确定，其它三个必然确定。而一个小正方形中是否存在依赖关系呢，答案是肯定的。所以再将正方形细分为两个三角形即可，一个三角形确定，小正方形确定，大正方形也确定了。这是总数sum。而有一些是涂色了的，个数便会减少，但是可以经过变换等价的点只能计算一次，详见代码。

题目地址：Palindrome graph

一直以为是mod=1e9+7，这个题目竟然是1e8+7。题目得看清！！

AC代码：

#include<iostream>  
#include<cstdio>  
#include<map>  
using namespace std;  
int n,len;  
const int mod=1e8+7;  //一直写的是1e9+7  
map<int,int> mp;  
  
void conver(int &x,int &y)  
{  
    while(1)  
    {  
        if(x<=len&&y<=len) break;  
        int tmp=x;  
        x=y;  
        y=n+1-tmp;  
    }  
    if(x<y) swap(x,y);  
}  
  
__int64 fastmi(__int64 base,__int64 p)  
{  
    __int64 ans=1;  
    while(p)  
    {  
        if(p&1)  
            ans=(ans*base)%mod;  
        base=(base*base)%mod;  
        p>>=1;  
    }  
    return ans;  
}  
  
int main()  
{  
    int m,k,i;  
    int x,y;  
    while(~scanf("%d%d%d",&n,&m,&k))  
    {  
        mp.clear();  
        len=(n+1)>>1;  
        int sum;  
        if(n&1) sum=(n/2+1)*(n/2+2)/2;  
        else sum=(n/2)*(n/2+1)/2;  
  
        for(i=1;i<=m;i++)  
        {  
            scanf("%d%d",&x,&y);  
            x++,y++;  
            conver(x,y);  
            x=10000*x+y;  
            if(!mp[x])  
            {  
                mp[x]=1;  
                sum--;  
            }  
        }  
  
        printf("%I64d\n",fastmi(k,sum));  
    }  
    return 0;  
}

补充：软件开发 , C++ ,

HDU 4365Palindrome graph(找规律 快速幂取模)

HDU 4365Palindrome graph(找规律快速幂取模)