题解:
由于本题数据范围较小,很容易想到状态压缩Dp的方式进行模拟,我们让dp[i][S]表示第i行的勇士状态为S(将s拆成二进制位,1表示该为有勇士)时的方案数,那么最后总的答案就为 ,所以直接枚举就可以啦!
注意要过滤掉其中一些非法状态,就是题目所说的那些,为了检测方便,可以将每行的状态转换为一个二进制数,直接位运算判断即可
代码
#include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll inf = 0x3f3f3f3f3f3f3f3f; const int mod = 100000000; const int maxn = 1e6 + 4; const int N = 5e3 + 5; const double eps = 1e-6; const double pi = acos(-1); ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} ll dp[13][(1<<12)+10]; int a[13],n,m; int main() { //freopen("RACE input.in","r",stdin); while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof dp); memset(a,0,sizeof a); for(int i=1;i<=n;i++) { for(int j=0;j<m;j++) { int x;scanf("%d",&x); a[i]|=(x<<j); } } int limit=1<<m; dp[0][0]=1; for(int i=1;i<=n;i++) { for(int x=0;x<limit;x++) { if((x&a[i])!=x) continue; if(x&(x>>1)) continue; for(int s=0;s<limit;s++) { if(s&x) continue; dp[i][x]=(dp[i-1][s]+dp[i][x])%mod; } } } ll ans=0; for(int i=0;i<limit;i++) ans=(ans+dp[n][i])%mod; printf("%lld\n",ans); } }