Cruel Bingo (AOJ2231)

問題:N*Nのビンゴ(ななめあり(対角線2つ))の盤面のうち,N*(N-1)個開いてるのにビンゴができてないCruelな盤面は何個あるか,ただし開いてることが確定してるマスがK個与えられる.N<=32,K<=8

知識0,頭5,ライブラリ0,実装1,英語0
気づけば一瞬ですね・・・
どのNマスを開かないマスにするか,を決めるとそいつらがタテ・ヨコ・ナナメ全てを妨害してればいいと言い換えられる.
まず上から埋めていくただのbitDPを思いつく.簡単.
つぎにななめがないなら,どこを埋めたか のうちK個以外はどこが埋まってても一緒なので32*2^8みたいなのができることがわかる.
しかしななめがあるとこの方法ではうまくやるのが難しい.
ななめに関して考えなくて済むような埋め方はないか?→真ん中から埋めれば良いのでは
きれいに1個ずつ埋めるのは不可能になるので,dp[i][j][k][l]=真ん中の(2i(+1))*(2i(+1))まででj個うめて,ななめが既に埋められているかどうか(k,l) を持つと更新できる.
K個に関しては,このまま扱うと面倒なので包除にすると楽に扱える(この行,列はもうおいちゃだめ というのを持ってそこにおかないようにするだけで済むのでDPで覚えなくて済む).
更新は新しく増えた周をななめの点4つと辺4つに分解して,それらを埋めるかどうか2^8をまわれば(実際これは無駄が多いので,事前に計算すると34状態くらいしかない)楽にできる.

計算量は 2^K * N * N/2 * 2 * 2 * 34 * 8 みたいなのになった.

まあ真ん中から埋めるということに気づきさえすれば普通のDPだし解いてみると1200+という気はしないなあ でも発想が面白くて好き.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,mod=10007;
vector<int> _bs;
inline int P(int x,int y){
	if(y==0) return 1;
	if(y==1) return x;
	if(y==2) return x*(x-1);
}
inline void add(int &x,int y){
	x+=y;
	x%=mod;
}
int solve(vector<int> x,vector<int> y){
	int K=x.size();
	int dp[17][33][2][2]={};		//	,put,sl,bsl
	bool banx[32]={},bany[32]={};
	bool sl=0,bsl=0;
	rep(i,K){
		if(banx[x[i]]||bany[y[i]]) return 0;
		banx[x[i]]=bany[y[i]]=1;
		if(x[i]==y[i]) bsl=1;
		if(x[i]+y[i]==N-1) sl=1;
	}
	dp[0][0][sl][bsl]=1;
	int L=-N%2,M=(N+1)/2;
	int A=(N-1)/2,B=N/2;
	rep(i,M){//it
		int X=0,Y=0;
		for(int j=A+1;j<=B-1;j++){
			if(!banx[j]) X++;
			if(!bany[j]) Y++;
		}
		rep(j,N+1-K){//put
			rep(k,2) rep(l,2){//sl,bsl
				if(dp[i][j][k][l]==0) continue;
				if(L==-1){
					add(dp[i+1][j][k][l],dp[i][j][k][l]);
					if(!banx[A]&&!bany[A]&&j+1<=N-K) add(dp[i+1][j+1][1][1],dp[i][j][k][l]);
				}else{
					for(int b:_bs){
						bool bs[8]={};
						int C=0;
						rep(a,8) bs[a]=(b>>a)&1;
						rep(a,8) if(bs[a]) C++;
						if(L==0&&(bs[4]||bs[5]||bs[6]||bs[7])) continue;
						if(banx[A]&&(bs[0]||bs[4]||bs[1])) continue;
						if(banx[B]&&(bs[2]||bs[6]||bs[3])) continue;
						if(bany[A]&&(bs[3]||bs[7]||bs[0])) continue;
						if(bany[B]&&(bs[1]||bs[5]||bs[2])) continue;
						int ad=P(Y-j,bs[4]+bs[6])*P(X-j,bs[5]+bs[7])%mod*dp[i][j][k][l];
						if(ad) add(dp[i+1][j+C][k|bs[1]||bs[3]][l|bs[0]|bs[2]],ad);
					}
				}
			}
		}
		A--,B++,L+=2;
	}
/*	rep(i,M+1) rep(j,N+1-K) rep(k,2) rep(l,2){
		printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,l,dp[i][j][k][l]);
	}
	puts("");*/
	return dp[M][N-K][1][1];
}
int xx[8],yy[8];
int main(){
	rep(i,1<<8){
		bool b[8]={};
		rep(j,8) b[j]=(i>>j)&1;
		bool ok=1;
		if(b[0]+b[4]+b[1]>1) ok=0;
		if(b[1]+b[5]+b[2]>1) ok=0;
		if(b[2]+b[6]+b[3]>1) ok=0;
		if(b[3]+b[7]+b[0]>1) ok=0;
		if(ok) _bs.pb(i);
	}
	int K;
	cin>>N>>K;
	rep(i,K) cin>>xx[i]>>yy[i];
	int ans=0;
	rep(i,1<<K){
		vector<int> x,y;
		rep(j,K) if((i>>j)&1) x.pb(xx[j]),y.pb(yy[j]);
		int t=1;
		if(x.size()%2) t=-1;
		int tmp=solve(x,y)*t;
//		show(i);
//		show(tmp);
		add(ans,tmp);
	}
	cout<<(ans+mod)%mod<<endl;
}