「CodePlus 2018 3 月赛」白金元首与莫斯科
$n leq 17,m leq 17$，$n*m$的01矩形，对每一个0问：当他单独变成1之后，在其他0处放多米诺牌（不一定放满，可以不放）的方案数。膜$1e9+7$。
直接$dp$是$n^42^n$，很难受。这种整体挖一块的东西可以用拼接法，就是用那一块前的$dp$值和那一块后的$dp$值计算答案。
$f(i,j,k)$--从$(1,1)$到$(i,j)$，在$(i,j)$前面$m$个格子状态$k$的方案数，$g(i,j,k)$--从$(n,m)$到$(i,j)$，在$(i,j)$后面$m$个格子状态$k$的方案数。状态$k$中1表示这一位是障碍或放了牌，0表示还没放。
然后来看$f(i,j,k)$和$g(i,j,k)$怎么合并出$(i,j)$的答案。画画图可以发现，$f(i,j,p)$和$g(i,j,q)$可以合并，除非他们空出的地方刚好对齐可以放竖的多米诺，表现为：$p,q$的第一位都是1，然后$p$和$q$的后$m-1$位恰好相反。因此可以$O(2^m)$算出一个点的答案。总复杂度$n^22^n$。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 //#include<math.h> 5 //#include<queue> 6 //#include<vector> 7 #include<algorithm> 8 //#include<iostream> 9 //#include<assert.h> 10 using namespace std; 11 12 int n,m; 13 const int mod=1e9+7; 14 int g[18][18][132222],f[2][132222],cur; 15 bool mp[18][18]; 16 17 int rev(int x) {int ans=x&1; for (int i=1;i<m;i++) ans|=((x>>i)&1)<<(m-i); return ans;} 18 19 int main() 20 { 21 scanf("%d%d",&n,&m); 22 for (int i=1;i<=n;i++) for (int j=1,x;j<=m;j++) scanf("%d",&x),mp[i][j]=x; 23 24 g[n][m][(1<<m)-1]=1; 25 for (int i=n;i;i--) 26 for (int j=m;j;j--) 27 { 28 int ni=i,nj=j-1; if (nj==0) ni=i-1,nj=m; if (ni==0) break; 29 for (int k=0,nk;k<(1<<m);k++) if (g[i][j][k]) 30 { 31 if ((k&1)==0 && i<n && !mp[i+1][j]) 32 {if (!mp[i][j]) {nk=(k>>1)|(1<<(m-1)); g[ni][nj][nk]+=g[i][j][k],g[ni][nj][nk]-=g[ni][nj][nk]>=mod?mod:0;}} 33 else 34 { 35 nk=(k>>1)|(1<<(m-1)); g[ni][nj][nk]+=g[i][j][k],g[ni][nj][nk]-=g[ni][nj][nk]>=mod?mod:0; 36 if (!mp[i][j]) 37 { 38 nk=(k>>1); g[ni][nj][nk]+=g[i][j][k],g[ni][nj][nk]-=g[ni][nj][nk]>=mod?mod:0; 39 if (j<m && ((k>>(m-1))&1)==0 && !mp[i][j+1]) 40 {nk=(k>>1)|(1<<(m-2))|(1<<(m-1)); g[ni][nj][nk]+=g[i][j][k],g[ni][nj][nk]-=g[ni][nj][nk]>=mod?mod:0;} 41 } 42 } 43 } 44 } 45 46 cur=0; f[0][(1<<m)-1]=1; 47 for (int i=1;i<=n;i++,puts("")) 48 for (int j=1;j<=m;j++) 49 { 50 int ans=0; 51 if (!mp[i][j]) 52 for (int k=1;k<(1<<m);k+=2) ans+=1ll*f[cur][k]*g[i][j][rev(k)]%mod,ans-=ans>=mod?mod:0; 53 printf("%d ",ans); 54 int ni=i,nj=j+1; if (nj>m) ni++,nj=1; if (ni>n) break; 55 for (int k=0,nk;k<(1<<m);k++) if (f[cur][k]) 56 { 57 if ((k&1)==0 && i>1 && !mp[i-1][j]) 58 {if (!mp[i][j]) {nk=(k>>1)|(1<<(m-1)); f[cur^1][nk]+=f[cur][k],f[cur^1][nk]-=f[cur^1][nk]>=mod?mod:0;}} 59 else 60 { 61 nk=(k>>1)|(1<<(m-1)); f[cur^1][nk]+=f[cur][k],f[cur^1][nk]-=f[cur^1][nk]>=mod?mod:0; 62 if (!mp[i][j]) 63 { 64 nk=(k>>1); f[cur^1][nk]+=f[cur][k],f[cur^1][nk]-=f[cur^1][nk]>=mod?mod:0; 65 if (j>1 && ((k>>(m-1))&1)==0 && !mp[i][j-1]) 66 {nk=(k>>1)|(1<<(m-1))|(1<<(m-2)); f[cur^1][nk]+=f[cur][k],f[cur^1][nk]-=f[cur^1][nk]>=mod?mod:0;} 67 } 68 } 69 f[cur][k]=0; 70 } 71 cur^=1; 72 } 73 return 0; 74 }
话说这代码调了好久的。。是个小错误，以后调代码得静下心了。