【BZOJ 4572】[SCOI2016] 围棋

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4572

这题的轮廓线DP的做法见:http://www.cnblogs.com/clrs97/p/5452790.html
然后,我们来说一说YJQ的神奇容斥:
首先大力感谢YJQ的支持!OI温暖满人间!
具体做法:枚举每一行的情况,搞一搞dp,顺便记录一下匹配次数的奇偶
然后因为是容斥,所以我们只需要管我们规定的匹配位置,其他位置都可以随意
于是可以预处理出转移,然后搞dp

代码方面,活生生把YJQ的5k+的代码压到了2k+
自己都觉得代码不可读 QAQ

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MOD = 1000000007;
const int REV = 333333336;
const int MAXN = 1 << 10;

int f[2][MAXN][2],trans[MAXN][MAXN],MX,n,m,c,q,N;
bool leg[MAXN],nxt[20][20],vis1[20],vis2[20],bit_cnt[MAXN];
char pat[2][10];

inline int pow(int w, int t) {
	int ret = 1;
	for (;t;w=(LL)w * w % MOD,t >>= 1) 
		if (t&1) ret = (LL)ret * w % MOD;
	return ret;
}

inline void prework() {
	memset(trans,0,sizeof(trans));
	for (int w=0,sign;w<=MX;w++) {
		leg[w] = sign = 1; bit_cnt[w] = __builtin_popcount(w)&1;
		for (int i=1;i<=N&&sign;i++) if (w&(1<<(i-1))) for (int j=i+1;j<=N&&sign;j++) if (w&(1<<(j-1)) && j-i < c) 
			for (int t=0;t<2&&sign;t++) for (int k=1;k<=c-j+i&&sign;k++) if (pat[t][k] != pat[t][j-i+k]) sign = leg[w] = 0;
	} 
	for (int i=1,sign;i<=N;i++) for (int j=1;j<=N;j++) {
		nxt[i][j] = sign = 1; if (abs(i-j+1) > c) continue;
		if (i < j) {for (int k=1;k<=c-j+i&&sign;k++) if (pat[0][k] != pat[1][j-i+k]) nxt[i][j] = sign = 0;}
		else for (int k=1;k<=c+j-i&&sign;k++) if (pat[1][k] != pat[0][i-j+k]) nxt[i][j] = sign = 0;
	}
	for (int w1=0;w1<=MX;w1++) if (leg[w1]) {
		memset(vis1,0,sizeof(vis1));  
		for (int i=1;i<=N;i++) if (w1&(1<<(i-1))) for (int j=0;j<c;j++) vis1[i+j] = 1;
		for (int w2=0,sign;w2<=MX;w2++) if (sign=1, leg[w2]){ 
			for (int i=1;i<=N;i++) if (w1&(1<<(i-1))) for (int j=1;j<=N;j++) if (w2&(1<<(j-1)) && !nxt[i][j]) sign = 0;
			if (!sign) continue; int tmp = 1; memset(vis2,0,sizeof(vis2));
			for (int i=1;i<=N;i++) if (w2&(1<<(i-1))) for (int j=0;j<c;j++) vis2[i+j] = 1;
			for (int i=1;i<=n;i++) if (!vis2[i]) tmp = tmp*3LL % MOD; else if (!vis1[i]) tmp = (LL)tmp*REV % MOD;
			trans[w1][w2] = tmp;
		}
	}
}

inline void solve() {
	int cur = 0, p = 1, vout = pow(3,n*m); 
	memset(f[p],0,sizeof(f[p])); f[p][0][0] = pow(3,n);
	for (int stp=2;stp<=m;stp++,cur^=1,p^=1) {
		memset(f[cur],0,sizeof(f[cur]));
		for (int w1=0;w1<=MX;w1++) for (int t=0;t<2;t++) if (f[p][w1][t]) 
			for (int w2=0;w2<=MX;w2++) (f[cur][w2][t^bit_cnt[w2]] += (LL)f[p][w1][t] * trans[w1][w2] % MOD) %= MOD;
	}
	for (int w=0;w<=MX;w++) (vout -= f[p][w][0]) %= MOD, (vout += f[p][w][1]) %= MOD;
	printf("%d\n",(vout%MOD+MOD)%MOD);
}	

int main(){
	cin>>m>>n>>c>>q;
	MX = (1 << (n - c + 1)) - 1; N = n - c + 1;
	for (int i=1;i<=q;i++) {
		scanf("%s%s",pat[0]+1,pat[1]+1);
		prework(); solve();
	} 
	return 0;
}

再次感谢YJQ的支持!容斥的做法真的好神!

【POJ 2411】Mondriaan’s Dream

题目传送门:http://poj.org/problem?id=2411

轮廓线dp

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = (1<<12)+9;

int n,m;
LL f[2][MAXN];

int main(){
	while (scanf("%d%d",&n,&m) && (n || m)) {
		int now=1, pre=0, MX=1<<n;
		memset(f[now],0,sizeof(f[now]));
		f[now][0] = 1;
		
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				swap(now, pre);
				memset(f[now],0,sizeof(f[now]));
				for (int k=0;k<MX;k++) if (f[pre][k]) {
					f[now][k^(1<<i-1)] += f[pre][k];
					if (i > 1 && k&(1<<i-2) && !(k&(1<<i-1)))
						f[now][k^(1<<i-2)] += f[pre][k];
				}
			}
		}
		printf("%lld\n",f[now][0]);
 	}
	return 0;
}