决战状压dp

决定在这个小巷里排兵布阵.小巷可以抽象成一个
们彼此之间并不是十分和♂谐.具体来说,一个哲学家会有一个
的矩形.每一位哲学家会占据一个格子.然而哲学家
的01矩阵来表示他自己的守备范围.
哲学家自己位于这个矩阵的(2,2)位置.具体的说,如果一个哲学家的守备矩阵是:
那么他的前后左右都不能有哲学家存在.
方案,答案对
手下有位哲学家.他需要你帮他求出有多少种排列这些哲学家的
取模.
定义两种排列方案不同,当且仅当存在一个位置在一种方案里面这个位置有哲学家,另一个位置没有.保证这个守
备矩阵的第二行第二列一定是1.
Data Range
对于前的数据,满足
对于前的数据,满足
另有
的数据,给出的守备矩阵只有第二行第二列为1
对于
的数据,
Sample Input I
3 2
0 1 0
0 1 1
1 0 0
Sample Output I
20

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #define RG register

 using namespace std;

 typedef long long ll;

 const int N=,mod=;

 ll f[][N*][<<];

 int n,m,num=,lim[][],a[<<+];

 int ct[][],s[];

 bool check(int x){

     if((lim[][] || lim[][]) && (x&(x<<)))return false;

     return true;

 }

 int getit(int x){

     int ret=;

     while(x){

         ret++;

         x-=(x&(-x));

     }

     return ret;

 }

 int w[<<];

 bool ok(int x,int y){

     if((lim[][] && ((x<<)&y)) || (lim[][] && ((y<<)&x)))return false;

     if((lim[][] && ((y<<)&x)) || (lim[][] && ((x<<)&y)))return false;

     if((lim[][] || lim[][]) && (x&y))return false;

     return true;

 }

 void work(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=;i++)

         for(int j=;j<=;j++){

             scanf("%d",&lim[i][j]);

          }

     int cnt=(<<)-;

     for(int i=;i<=cnt;i++)w[i]=getit(i);

     for(int i=;i<=cnt;i++){

         if(check(i))a[++num]=i,f[][w[i]][num]=;

     }

     for(int i=;i<=num;i++)

         for(int j=;j<=num;j++)if(ok(a[i],a[j]))ct[i][++s[i]]=j;

     int c=,co=,p;

     for(RG int i=;i<=n;i++){

         for(RG int k=;k<=m;k++)

         for(RG int j=;j<=num;j++){

             f[co][k][j]=;

             p=k-w[a[j]];

             if(k>=w[a[j]])

             for(RG int g=;g<=s[j];g++){

                 f[co][k][j]+=f[c][p][ct[j][g]],f[co][k][j]%=mod;

             }

         }

         c^=;co^=;

     }

     ll ans=;

     for(int i=;i<=num;i++)ans+=f[c][m][i],ans%=mod;

     printf("%lld\n",ans);

 }

 int main()

 {

     freopen("final.in","r",stdin);

     freopen("final.out","w",stdout);

     work();

     return ;

 }

决战 状压dp

相关文章