Game

题目大意

给出一个n*m的网格图，一个格子可以选择是否选取，每一行给出一个限制，要求该行连通块(一个连通块之间没有格子是不取的，且至少有一个格子被选取)的个数等于a[i],每一列也给出一个要求，要求该列连通块的个数等于b[i]，即一共有n+m个限制，求有多少种选取方案。输出方案数mod(10^9+7)的值。 n<=5,m<=20。

dp

求方案数通常做法都是dp。。。 设f[i][j][k]表示做到第i列且第i列的状态为j，当前n行的状态为k的方案数。 枚举i是O(m)的,枚举j是O(2^n)的,枚举k是O((m+1)^n)的，转移是O(2^n)的 这个是比较naive的dp，接下来我们考虑优化。 枚举i是肯定省不了的了。 而枚举j，由于第i列是有限制的，设t[i]表示第i列合法的状态数，考虑n=5时: b[i]=1时t[i]=5+4+3+2+1=15 b[i]=2时t[i]=14 b[i]=3时t[i]=1 也就是状态数最多为15，转移也是相同，所以这部分的复杂度<=O(15^2) 再考虑每一行连通块的个数最多为(m+1)/2所以枚举k只需O(((m/2)+1)^n) 而且每一行也是有限制的，所以合法的状态也很少。 加上这些优化就可以跑过了。。

代码

#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) #define ll long long using namespace std; const int maxn=11;const int ma=161050+5;const int mo=1000000007; int f[2][32][ma],i,j,n,m,l,k,ms,ans,k1; int w1[maxn*2][ma]; int a[maxn],b[maxn*2],mm; int w[maxn*2][32]; bool pc(int s,int y){ int x=0,x1=0,t=0; while (s){ x=s%2;if (x&&!x1) t++; s/=2,x1=x; } if (t==y) return 1;return 0; } bool pd(int x,int s){ int c[6],t=n,i,w=0; fo(i,1,n) c[i]=0; while (s){ c[t]=s%11,s/=11; if (c[t]>a[t]) return 0;t--; } fo(i,1,n) if ((m-x+1)/2+c[i]<a[i]) return 0; return 1; } bool pp(int s1,int s2,int k){ int c[6],t=n,i,x,y; fo(i,1,n) c[i]=0; while (k)c[t--]=k%11,k/=11; t=n; while (s1||s2) { x=s1%2,y=s2%2; if (x&&!y) { c[t]++; if (c[t]>a[t]) return 0; } t--; s1/=2,s2/=2; } mm=0; fo(i,1,n) mm=mm*11+c[i]; return 1; } int main(){ scanf("%d%d",&n,&m); fo(i,1,n) scanf("%d",&a[i]); fo(i,1,m) scanf("%d",&b[i]); fo(i,1,n) if (a[i]>((m+1)/2)) { printf("0\n"); return 0; } fo(i,1,m) if (b[i]>((n+1)/2)){ printf("0\n"); return 0; } ms=0; fo(i,1,n) ms=ms*11+a[i]; fo(i,1,m) fo(j,0,ms) if (pd(i,j)) w1[i][++w1[i][0]]=j; int s=(1<<n)-1; fo(i,1,m) fo(j,0,s) if (pc(j,b[i])) w[i][++w[i][0]]=j; f[0][0][0]=1; w[0][0]=1,w[0][1]=0;w1[0][0]=1;w1[0][1]=0; fo(i,1,m) { int ii=i%2,i1=1-ii; memset(f[ii],0,sizeof(f[ii])); fo(j,1,w[i][0]){ int s=w[i][j]; fo(l,1,w[i-1][0]) { int s1=w[i-1][l]; fo(k1,1,w1[i-1][0]) { k=w1[i-1][k1]; if (f[i1][s1][k]) { if (pp(s,s1,k)) f[ii][s][mm]=(f[ii][s][mm]+f[i1][s1][k])%mo; } } } } } fo(i,1,w[m][0]) ans=(ans+f[m%2][w[m][i]][ms])%mo; printf("%d\n",ans); }