Luogu

算法

这题和炮兵阵地是类似的，而且不需要滚动数组。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const int MOD=100000000;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int S[1<<12],sum[1<<12],cnt=0;
int f[13][1<<12];
int cv[13];

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++) {
            int k=read();
            if (!k) cv[i]|=(1<<j-1);
        }
    for (re int i=0;i<1<<m;i++) {
        if (i&(i<<1)) continue;
        S[++cnt]=i; int j=i;
        while (j) j>>=1,sum[cnt]++;
        if (!(S[cnt]&cv[1])) f[1][cnt]=1;
    }
    for (re int i=2;i<=n;i++) {
        for (re int j=1;j<=cnt;j++) {
            if (S[j]&cv[i]) continue;
            for (re int k=1;k<=cnt;k++) {
                if (S[j]&S[k]) continue;
                (f[i][j]+=f[i-1][k])%=MOD;
            }
        }
    }
    int ans=0;
    for (re int i=1;i<=cnt;i++) (ans+=f[n][i])%=MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改：2019 年 09 月 24 日 01 : 23 PM
© 允许规范转载