読者です 読者をやめる 読者になる 読者になる

AOJ 2231: Cruel Bingo

これはブログに記事を書きます Advent Calendar 2014 - Adventarの12日目の記事です。


天啓DP。
真ん中の正方形区画から外側に向かってDPすることに気がついたらあとは超絶面倒な遷移を作ってDPするだけなんだけど、それに気がつかないから1200+なわけでして。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int mod=10007;
int r[10];
int c[10];
int n;
int dp[40][40][4];
int dp2[40][40][4][4][5][3];
int v[40][40];
int calc(vector<pair<int,int> > p){
	for(int i=0;i<40;i++)for(int j=0;j<40;j++)for(int k=0;k<4;k++)
		dp[i][j][k]=0;
	for(int i=0;i<p.size();i++)for(int j=i+1;j<p.size();j++){
		if(p[i].first==p[j].first||p[i].second==p[j].second)return 0;
	}
	for(int i=0;i<40;i++)for(int j=0;j<40;j++)v[i][j]=0;
	for(int i=0;i<p.size();i++){
		v[p[i].first][p[i].second]=1;
	}
	dp[0][0][0]=1;
	bool ok=true;
	for(int i=0;i<p.size();i++)if(n/2==p[i].first||n/2==p[i].second)ok=false;
	if(n%2&&ok)dp[0][1][3]=1;
	for(int i=0;i<n/2;i++){
		int hu=0;
		int wu=0;
		int he=0;
		int we=0;
		for(int j=0;j<p.size();j++){
			if(p[j].first==n/2-1-i)he|=1;
			if(p[j].first==(n+1)/2+i)he|=2;
			if(p[j].second==n/2-1-i)we|=1;
			if(p[j].second==(n+1)/2+i)we|=2;
			if(n/2-1-i<p[j].first&&p[j].first<(n+1)/2+i)hu++;
			if(n/2-1-i<p[j].second&&p[j].second<(n+1)/2+i)wu++;
		}
	//	printf("%d: %d %d %d %d\n",i,hu,wu,he,we);
		for(int j=0;j<40;j++){
			for(int k=0;k<4;k++){
				if(!dp[i][j][k])continue;
		//		if(i*2+n%2-j-hu<0||i*2+n%2-j-wu<0)printf("%d %d %d: %d %d %d\n",i,j,k,dp[i][j][k],hu,wu);
				if(i*2+n%2-j-hu<0||i*2+n%2-j-wu<0)continue;
				for(int l=0;l<=4;l++){
					dp[i+1][j+l][k]=(dp[i+1][j+l][k]+dp[i][j][k]*dp2[i*2+n%2-j-hu][i*2+n%2-j-wu][he][we][l][0])%mod;
					dp[i+1][j+l][k|1]=(dp[i+1][j+l][k|1]+dp[i][j][k]*dp2[i*2+n%2-j-hu][i*2+n%2-j-wu][he][we][l][1])%mod;
					dp[i+1][j+l][k|2]=(dp[i+1][j+l][k|2]+dp[i][j][k]*dp2[i*2+n%2-j-hu][i*2+n%2-j-wu][he][we][l][2])%mod;
				}
			}
		}
	}
	int ret=dp[n/2][n-(int)p.size()][3];
	bool t1=false;
	bool t2=false;
	for(int i=0;i<p.size();i++){
		if(p[i].first==p[i].second)t1=true;
		if(p[i].first+p[i].second==n-1)t2=true;
	}
	if(t1)ret=(ret+dp[n/2][n-(int)p.size()][2])%mod;
	if(t2)ret=(ret+dp[n/2][n-(int)p.size()][1])%mod;
	if(t1&&t2)ret=(ret+dp[n/2][n-(int)p.size()][0])%mod;
	return ret;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	n=a;
	for(int i=0;i<b;i++)scanf("%d%d",r+i,c+i);
	int ret=0;
	for(int i=0;i<40;i++)for(int j=0;j<40;j++){
		for(int k=0;k<4;k++)for(int l=0;l<4;l++){
			dp2[i][j][k][l][0][0]=1;
			int s1=2-__builtin_popcount(k);
			int s2=2-__builtin_popcount(l);
			dp2[i][j][k][l][1][0]=i*s2+j*s1;
			dp2[i][j][k][l][2][0]=(i*(i-1)*(s2/2)+j*(j-1)*(s1/2)+i*j*s1*s2)%mod;
			if(s1==1&&s2==2){
				dp2[i][j][k][l][3][0]=j*i*(i-1)%mod;
			}
			if(s1==2&&s2==1){
				dp2[i][j][k][l][3][0]=i*j*(j-1)%mod;
			}
			if(s1==2&&s2==2){
				dp2[i][j][k][l][3][0]=(j*i*(i-1)+i*j*(j-1))*2%mod;
				dp2[i][j][k][l][4][0]=i*(i-1)*j*(j-1)%mod;
			}
			int t1=0;
			int t2=0;
			if(!(k&1)&&!(l&1))t1++;
			if(!(k&2)&&!(l&2))t1++;
			if(!(k&1)&&!(l&2))t2++;
			if(!(k&2)&&!(l&1))t2++;
			dp2[i][j][k][l][1][1]=t1;
			dp2[i][j][k][l][1][2]=t2;
			if(t1==2){
				dp2[i][j][k][l][2][1]=2*(i+j)+1;
				dp2[i][j][k][l][3][1]=2*i*j;
			}else if(t1==1&&k==0)dp2[i][j][k][l][2][1]=j;
			else if(t1==1&&l==0)dp2[i][j][k][l][2][1]=i;
			if(t2==2){
				dp2[i][j][k][l][2][2]=2*(i+j)+1;
				dp2[i][j][k][l][3][2]=2*i*j;
			}else if(t2==1&&k==0)dp2[i][j][k][l][2][2]=j;
			else if(t2==1&&l==0)dp2[i][j][k][l][2][2]=i;
		}
	}
//	for(int i=0;i<5;i++)for(int j=0;j<5;j++){
//		for(int k=0;k<=4;k++)printf("%d %d %d: %d\n",i,j,k,dp2[i][j][1][0][k][0]);
//	}
	for(int i=0;i<(1<<b);i++){
		int t=__builtin_popcount(i);
		vector<pair<int,int> > p;
		for(int j=0;j<b;j++)if(i&(1<<j))p.push_back(make_pair(r[j],c[j]));
		int val=calc(p);
	//	printf("%d: %d\n",i,val);
		if(t%2)ret=(ret+mod-val)%mod;
		else ret=(ret+val)%mod;
	}
	printf("%d\n",ret);
}