题目传送门: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的支持!容斥的做法真的好神!