首页 > 代码库 > HDU 4365

HDU 4365

2024-07-20 11:31:07   214人阅读

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

当未涂色时，若要符合要求，则必须要求每一圈矩形都是上下左右对称的。注意是一圈的小矩形。对于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


联系
我们