【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的支持!容斥的做法真的好神!

22 thoughts to “【BZOJ 4572】[SCOI2016] 围棋”

  1. I have been browsing online more than three hours today, yet I never found any interesting article like yours.
    It’s pretty worth enough for me. In my view,
    if all web owners and bloggers made good content as you did, the web will be a lot more useful than ever before.

  2. I’d like to thank you for the efforts you have put in writing this website.
    I really hope to see the same high-grade blog
    posts by you later on as well. In fact, your creative writing abilities has encouraged me to get my own site
    now 😉

  3. I do not even know how I ended up here, but I thought this
    post was great. I don’t know who you are but certainly
    you are going to a famous blogger if you aren’t already 😉 Cheers!

  4. Nice post. I learn something totally new and challenging on blogs I stumbleupon everyday.

    It’s always useful to read content from other authors and
    practice a little something from their websites.

  5. Thank you for any other informative site. Where else could I
    am getting that type of info written in such a perfect approach?
    I’ve a mission that I’m just now operating on, and I’ve been at the look
    out for such info.

  6. Hey there I am so happy I found your weblog, I really found you by mistake,
    while I was researching on Bing for something else, Regardless I am here now and would just like to say thanks for a remarkable post and a all round entertaining blog (I also love the theme/design), I don’t
    have time to browse it all at the minute but I have bookmarked it and also
    included your RSS feeds, so when I have time I will be back to read
    more, Please do keep up the great work.

  7. I’m truly enjoying the design and layout of your website.

    It’s a very easy on the eyes which makes it much
    more pleasant for me to come here and visit more often.
    Did you hire out a designer to create your theme?
    Great work!

  8. Hey! I could have sworn I’ve been to this website before but after browsing through some of the post
    I realized it’s new to me. Anyhow, I’m definitely delighted
    I found it and I’ll be bookmarking and checking back often!

  9. Undeniably believe that which you said. Your favourite
    reason seemed to be on the web the easiest factor to have in mind of.

    I say to you, I certainly get annoyed whilst people consider concerns that they just
    do not realize about. You managed to hit the nail upon the top and also defined out the entire thing without having
    side-effects , folks could take a signal. Will likely be again to get more.
    Thanks

  10. Good way of explaining, and pleasant piece of writing to obtain data regarding my presentation subject matter, which i am going to deliver in school.

  11. I absolutely love your site.. Very nice colors & theme. Did you
    build this amazing site yourself? Please reply back as I’m planning to create my own website and would
    love to learn where you got this from or just what the theme
    is named. Cheers!

  12. Hello my loved one! I want to say that this article is amazing, nice written and include approximately all important infos. I would like to peer extra posts like this .

Leave a Reply

Your email address will not be published. Required fields are marked *