poj 3524 Corn Fields

[TOC]
题目链接：http://poj.org/problem?id=3254
取模竟然不是1e9+7。。。。
//#include"bits/stdc++.h"
#include"iostream"
#include"cstring"
#include"vector"
using namespace std;
typedef long long LL;
const int maxn=13;
const int MOD=1e8;
LL dp[maxn][1<<maxn];
int row[maxn]; 
int main()
{
    int N,M;
    while(cin>>N>>M)
    {
        memset(dp,0,sizeof dp);
        for(int i=0;i<N;i++)
        {
            row[i]=0;
            for(int j=1;j<=M;j++)
            {
                int t;
                cin>>t;
                if(t)row[i]|=(1<<(M-j));                //记录输入的图是什么样子 
            }
        }
        vector<int>STA;
        for(int sta=0;sta<(1<<M);sta++)
        {
            if(sta&(sta<<1))continue;
            STA.push_back(sta);             //筛选出所有的合法状态 
            dp[0][sta]=1;                   //第一行的合法转态赋初值 
        }

        for(int i=1;i<N;i++)
        {
            for(int j=0;j<STA.size();j++)
            {

                if((STA[j]&row[i])!=STA[j])continue;//说明当前这这状态不符合这块地的要求 
                for(int k=0;k<STA.size();k++)//枚举上一层的状态，合法的就加到这一层上 
                {
                    if((STA[k]&row[i-1])!=STA[k])continue;
                    if(STA[j]&STA[k])continue;//说明这两种状态有冲突
                    dp[i][STA[j]]+=dp[i-1][STA[k]];//把上一层的方案数加到这一层 
                    dp[i][STA[j]]%=MOD;
                }
            }
        }
        LL ans=0;
        for(int i=0;i<STA.size();i++)
        {
            if((STA[i]&row[N-1])==STA[i])ans+=dp[N-1][STA[i]];//这个判断不能少，我WA了好多发T_T 
            ans%=MOD;
        }
        cout<<ans<<endl;
    }
}