先求出不考虑分割线的n*m棋盘的覆盖方案数记为f[n][m]

然后枚举列分割线的状态（状压），计算此时不存在行分割线的方案数

求出这个我们就可以用容斥原理算出答案了

怎么算在列分割线确定的情况下，不存在行分割线的方案数呢？

记s[i]=f[i][a1]*f[i][a2]*...表示在有i行不考虑行分割线且列分割线分成a1,a2...ak块的方案数

则到第i行不存在行分割线的方案数g[i]=s[i]-∑ g[j]*s[i-j] (1<=j<i) 

相当于补集转化，求第一条行分割线为j时不合法的方案数……

一开始把答案都预处理出来即可

1 #include
      
        2  3 using namespace std; 4 const int mo=1e9+7; 5 int n,m; 6 int ans[20][20],f[20][20],s[20],g[20],q[20]; 7 void inc(int &a,int b) 8 { 9     a+=b;10     if (a>=mo) a-=mo;11 }12 struct node13 {14     int st[1<<16],f[1<<16],len;15     void clr()16     {17         for (int i=1; i<=len; i++) f[st[i]]=0;18         len=0;19     }20     void push(int nw,int w)21     {22         if (f[nw]==0) st[++len]=nw;23         inc(f[nw],w);24     }25  } h[2];26 27  void get()28  {29      for (int m=1; m<=16; m++)30      {31          int p=0; h[1].clr(); h[0].clr();32          h[0].push(0,1);33          for (int i=1; i<=16; i++)34          {35             for (int j=0; j
       
        >(j-1)&1)) h[p].push(st|(1<<(j-1))|(1<
        
         >j&1)48                     {49                         if (j&&!(st>>(j-1)&1)) h[p].push(st|(1<<(j-1)),w);50                         h[p].push(st^(1<
         
          >k&1) q[++t]=k+1;70             q[t+1]=m;71             for (int i=1; i<=16; i++)72             {73                 s[i]=1;74                 for (int j=1; j<=t+1; j++)75                     s[i]=1ll*s[i]*f[i][q[j]-q[j-1]]%mo;76             }77             for (int i=1; i<=16; i++)78             {79                 g[i]=s[i];80                 for (int j=1; j