これはブログに記事を書きます 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); }
