状压DP

``` #include<cstdio> #include<iostream> #include<cctype> #define mod 100000000 using namespace std; int n,m,tot,state[1500],dp[15][1500],ans,cur[15]; //dp[行数][状态数] //state 预存的可能情况 //cur每行的情况 inline bool fit(int x,int k) //判断当前状态是否符合当前行 { return !(state[x]&cur[k]); } inline void init() //初始化 { int sum=1<<n,i; //列举可能状态，并预存 for (i=0;i<sum;i++) if (!(i&(i<<1))) state[++tot]=i; } int main() { int i,j,k; scanf("%d%d",&m,&n); init(); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { scanf("%d",&k); if(!k)cur[i]+=(1<<(n-j));//cur不合法为1 } for(int i=1;i<=tot;i++)//初始化第一行 if(fit(i,1))dp[1][i]=1; for(int i=2;i<=m;i++) for(int j=1;j<=tot;j++) { if(!fit(j,i))continue; for(int k=1;k<=tot;k++) { if(!fit(k,i-1))continue; if(state[j]&state[k])continue; dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; } } for(int i=1;i<=tot;i++)ans=(ans+dp[m][i])%mod; printf("%d",ans); } ```