M_sea

洛谷1879 玉米田Corn Fields
题目描述传送门算法这题和炮兵阵地是类似的,而且不需要滚动数组。细节见代码。代码#include <bits/...
扫描右侧二维码阅读全文
08
2018/09

洛谷1879 玉米田Corn Fields

题目描述

传送门

算法

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

细节见代码。

代码

#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;
}
最后修改:2018 年 11 月 09 日 05 : 25 PM

发表评论

2 条评论

  1. yyb

    M_sea好强啊。

    1. M_sea
      @yyb

      您好fAKe啊 qwq