AOJ 2231 : Cruel Bingo

解法

包除原理+DP

包除原理に気づかずbitDPしようとしたら複雑すぎて無理だった(解説スライド見ても解けるとしか書いてなかった)
あと、解説スライド見ると包除原理だけで良いらしい(ちょっと読んでもよく分からなかった)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long ll;
#define N 40
#define M 8
ll ux[N], uy[N], g[N][N], dp[N][N][4], dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
ll mod = 10007;
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int s = n&1, t = n/2, t2 = (n-1)/2;
	for(int i = 0; i < m; i++){
		int x, y;
		scanf("%d%d",&x,&y);
		ux[x] |= 1<<i;
		uy[y] |= 1<<i;
	}
	ll res = 0;
	for(int i = 0; i < 1<<m; i++){
		int bt = __builtin_popcount(i);
		int dg = 0;
		bool ok = true;
		for(int j = 0; j < n; j++){
			if(__builtin_popcount(ux[j]&i)>1 || __builtin_popcount(uy[j]&i)>1){
				ok = false;
			}
			for(int k = 0; k < n; k++){
				g[j][k] = (ux[j]|uy[k])&i;
				if(ux[j]&uy[k]&i){
					if(j==k) dg |= 1;
					if(j==n-k-1) dg |= 2;
				}
			}
		}
		if(!ok) continue;
		memset(dp, 0, sizeof(dp));
		dp[0][bt][dg] = 1;
		if(s&&!g[t][t]) dp[0][bt+1][3] = 1;
		for(int j = 1; j <= t; j++){
			int left = t-j;
			int len = 2*j+s;
			int fr[4] = {}, fr2[4] = {};
			for(int k = 0, a = left, b = left; k < 4; k++){
				for(int l = 0; l < len-1; l++, a+=dx[k], b+=dy[k]){
					if(!g[a][b]){
						if(l==0) fr2[k] = 1;
						else fr[k]++;
					}
				}
			}
			for(int k = bt; k <= n; k++){
				int ms = k-bt;
				int fr3[4], fr4[2];
				for(int l = 0; l < 4; l++) fr3[l] = max(0, fr[l]-ms);
				fr4[0] = max(0, fr3[0]*(fr3[2]-1));
				fr4[1] = max(0, fr3[1]*(fr3[3]-1));
				for(int l = 0; l < 4; l++){
					int dd = dp[j-1][k][l];
					(dp[j][k][l]+=dd)%=mod;
					(dp[j][k+1][l]+=(fr3[0]+fr3[1]+fr3[2]+fr3[3])*dd)%=mod;
					(dp[j][k+1][l|1]+=(fr2[0]+fr2[2])*dd)%=mod;
					(dp[j][k+1][l|2]+=(fr2[1]+fr2[3])*dd)%=mod;
					(dp[j][k+2][l]+=(fr3[0]*fr3[1]+fr4[0]+fr3[0]*fr3[3]+fr3[1]*fr3[2]+fr4[1]+fr3[2]*fr3[3])*dd)%=mod;
					(dp[j][k+2][l|1]+=(fr2[0]*(fr3[1]+fr3[2])+fr2[2]*(fr3[3]+fr3[0])+fr2[0]*fr2[2])*dd)%=mod;
					(dp[j][k+2][l|2]+=(fr2[1]*(fr3[2]+fr3[3])+fr2[3]*(fr3[0]+fr3[1])+fr2[1]*fr2[3])*dd)%=mod;
					(dp[j][k+3][l]+=(fr4[0]*(fr3[1]+fr3[3])+fr4[1]*(fr3[0]+fr3[2]))*dd)%=mod;
					(dp[j][k+3][l|1]+=(fr2[0]*(fr3[1]*fr3[2])+fr2[2]*(fr3[3]*fr3[0]))*dd)%=mod;
					(dp[j][k+3][l|2]+=(fr2[1]*(fr3[2]*fr3[3])+fr2[3]*(fr3[0]*fr3[1]))*dd)%=mod;
					(dp[j][k+4][l]+=(fr4[0]*fr4[1])*dd)%=mod;
				}
			}
		}
		(res+=dp[t][n][3]*(bt&1?-1:1))%=mod;
	}
	printf("%ld\n",(res+mod)%mod);

	return 0;
}