决战状压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

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #define RG register
 8 using namespace std;
 9 typedef long long ll;
10 const int N=2505,mod=998244353;
11 ll f[2][N*3][1<<3];
12 int n,m,num=0,lim[4][4],a[1<<3+5];
13 int ct[15][15],s[15];
14 bool check(int x){
15     if((lim[2][1] || lim[2][3]) && (x&(x<<1)))return false;
16     return true;
17 }
18 int getit(int x){
19     int ret=0;
20     while(x){
21         ret++;
22         x-=(x&(-x));
23     }
24     return ret;
25 }
26 int w[1<<3];
27 bool ok(int x,int y){
28     if((lim[1][1] && ((x<<1)&y)) || (lim[1][3] && ((y<<1)&x)))return false;
29     if((lim[3][1] && ((y<<1)&x)) || (lim[3][3] && ((x<<1)&y)))return false;
30     if((lim[1][2] || lim[3][2]) && (x&y))return false;
31     return true;
32 }
33 void work(){
34     scanf("%d%d",&n,&m);
35     for(int i=1;i<=3;i++)
36         for(int j=1;j<=3;j++){
37             scanf("%d",&lim[i][j]);
38          }
39     int cnt=(1<<3)-1;
40     for(int i=0;i<=cnt;i++)w[i]=getit(i);
41     for(int i=0;i<=cnt;i++){
42         if(check(i))a[++num]=i,f[0][w[i]][num]=1;
43     }
44     for(int i=1;i<=num;i++)
45         for(int j=1;j<=num;j++)if(ok(a[i],a[j]))ct[i][++s[i]]=j;
46     int c=0,co=1,p;
47     for(RG int i=2;i<=n;i++){
48         for(RG int k=0;k<=m;k++)
49         for(RG int j=1;j<=num;j++){
50             f[co][k][j]=0;
51             p=k-w[a[j]];
52             if(k>=w[a[j]])
53             for(RG int g=1;g<=s[j];g++){
54                 f[co][k][j]+=f[c][p][ct[j][g]],f[co][k][j]%=mod;
55             }
56         }
57         c^=1;co^=1;
58     }
59     ll ans=0;
60     for(int i=1;i<=num;i++)ans+=f[c][m][i],ans%=mod;
61     printf("%lld
",ans);
62 }
63 int main()
64 {
65     freopen("final.in","r",stdin);
66     freopen("final.out","w",stdout);
67     work();
68     return 0;
69 }

决战 状压dp

决战状压dp