萌新刚学OI,求助
查看原帖
萌新刚学OI,求助
122720
W_Y_Z楼主2020/8/18 20:35

下面为AC代码

但有玄学判断不知道为什么

具体在代码里

#include<bits/stdc++.h>
#define int long long 
const int maxn=13;
const int mod=100000000;
using namespace std;
inline int read(){
    int x=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
inline int max(const int &a,const int &b) { return a>b?a:b; }
inline int min(const int &a,const int &b) { return a<b?a:b; }
int n,m;
int tot[378],cnt;
int dp[378][maxn];
int op[maxn];
signed main(void){
    n=read(),m=read();
    for(register int i = 0 ; i < ( 1 << m ) ; ++i) if( ( i & ( i >> 1 ) ) == 0 ) tot[++cnt]=i;
    // cout<<cnt<<endl;
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j)
            op[i]|= ((!read())<<(j-1));
    }
    // cout<<op[1]<<endl;
    // dp[1][0]=1;
    if(n==1&&m==1){
        if(op[1]==1) printf("1\n");
        else printf("2\n");
        return 0;
    }
    for(register int i=1;i<=cnt;++i)
     //   if((op[1]&i)==0) 没错就是他,去掉以后AC
            dp[i][1]=1;
    for(register int i=2;i<=n;++i){
        for(register int j=1;j<=cnt;++j)
            for(register int k=1;k<=cnt;++k){  
                if((op[i]&tot[j])||(op[i-1]&tot[k])||(tot[k]&tot[j])) continue;
                // cout<<i<<' '<<j<<' '<<k<<' '<<dp[j][i]<<' '<<dp[k][i-1]<<endl;
                (dp[j][i]+=dp[k][i-1])%=mod;
            }
    }
    int ans=0;
    for(register int i=1;i<=cnt;++i) (ans+=dp[i][n])%=mod;
    printf("%lld\n", ans);
    return 0;
}
/*
4 10
0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
0 0 1 1 1 1 1 1 1 0
4402955
*/
2020/8/18 20:35
加载中...