【题目分析】 状压DP
【代码】万恶的位运算。
#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int x,rank[500],cnt=0,ans=0; int dp[15][500]; int map[15]; int main() { int n,m; scanf("%d%d",&n,&m); for (int i=0;i<(1<<m);++i) if (!(i&(i<<1))) rank[++cnt]=i; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) { scanf("%d",&x); if (x) map[i]|=(1<<(m-j)); } dp[0][1]=1; for (int i=1;i<=n;++i) for (int j=1;j<=cnt;++j) for (int k=1;k<=cnt;++k) if (((map[i]|rank[k])>map[i])||((rank[j]&rank[k]))) continue; else (dp[i][k]+=dp[i-1][j])%=100000000; for (int i=1;i<=cnt;++i) (ans+=dp[n][i])%=100000000; printf("%d\n",ans%100000000); }