HDU 4365

把涂色的格子按对称旋转至左上角。

当未涂色时，若要符合要求，则必须要求每一圈矩形都是上下左右对称的。注意是一圈的小矩形。对于N*N的阵，若最外层一圈的小矩形要符合要求，则（假设N%2==0）可以涂色的种数为K^（N/2）种。全个矩阵可涂色数为K^(N/2)*(N/2+1)/2。

接第一段，(N/2)*(N/2+1)/2即为左上角矩形的对角线以上的小矩形数。若移动后有小矩形被涂色，减去即可。

今天才做了两题。这一题的规律是在吃饭时想到的，而上一题，卡在了那个公式上。

好可怜的人啊。。。。还有一题，是组合数学，果然放弃了，不想做组合数学的题。

。。。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int Mod=100000007;

struct Paint{

	int x,y;

}Ed[2050];

bool cmp(Paint a,Paint b){

	if(a.x<b.x) return true;

	else if(a.x==b.x){

		if(a.y<b.y)return true;

	}

	return false;

}

int quick(long long  a,long long  b,long long m){

	long long  ans=1;

    while(b){

        if(b&1){

            ans=(ans*a)%m;

        }

        b>>=1;

        a=(a*a)%m;

    }

    return (int)ans;

}

int main(){

	int n,m,k,pi;

	while(scanf("%d%d%d",&n,&m,&k)!=EOF){

		for(int i=0;i<m;i++){

			scanf("%d%d",&Ed[i].x,&Ed[i].y);

			Ed[i].x++; Ed[i].y++;

		}

		if(n%2)

		n++;

		pi=n/2;

		pi=pi*(pi+1)/2;

		int mid=n/2;

		for(int i=0;i<m;i++){

			if(Ed[i].x>mid) Ed[i].x=(n+1)-Ed[i].x;

			if(Ed[i].y>mid) Ed[i].y=n+1-Ed[i].y;

			if(Ed[i].x>Ed[i].y){

				int tmp=Ed[i].y;

				Ed[i].y=Ed[i].x;

				Ed[i].x=tmp;

			}

		}

		sort(Ed,Ed+m,cmp);

		if(m>=1) pi--;

		for(int i=1;i<m;i++){

			if(Ed[i].x==Ed[i-1].x&&Ed[i].y==Ed[i-1].y)

			continue;

			pi--;

		}

		printf("%d\n",quick((long long)k,(long long)pi,(long long)Mod)%Mod);

	}

	return 0;

}

巴特西

HDU 4365

最新文章

热门文章