Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 代码

Posted by phython at 2017-03-07 21:49:31 on Problem 3254
```#include <cstdio>
#include <iostream>
using namespace std;
int M,N;
const int MOD = 100000000;
int dp[1<<13][20];//dp[state][i]
int map[20];
int cnt;
int state[1<<13];
int solve()
{
//初始化工作
for(int S = 0;S < (1<<N);S++) {if((S&(S<<1)) == 0) state[cnt++] = S;}
for(int i = 0;i < cnt;++i) if((state[i]&map[0]) == 0) dp[state[i]][0] = 1;
for(int i = 1;i < M;i++)
{
for(int j = 0;j < cnt;j++)
{
if(state[j]&map[i]) continue;
for(int k = 0;k < cnt;++k)
{
if(state[j]&state[k] ) continue;
dp[state[j]][i] = (dp[state[j]][i] + dp[state[k]][i-1])%MOD;
}
}
}
int ans = 0;
for(int i = 0;i < cnt;++i) /*if(state[i]&map[M-1] != 0 )*/ ans = (ans + dp[state[i]][M-1])%MOD;
return ans;
}
int main()
{
cin>>M>>N;
for(int i = 0;i < M;i++)
{
for(int j = 0;j < N;j++)
{
int tem;cin>>tem;
if(!tem) map[i] |= 1<<(N-j-1);
}
}
cout<<solve()<<endl;
return 0;
}
```

Followed by: