HDU

因为第一列的状态一确定，那么它后一列的状态就可以确定了，而且第一列的状态就有3种，0个雷，1个雷，2个雷，所以可以枚举第一列的状态，求出在第一列状态确定的情况下这n列的方案数，然后对贡献求和即可。有几个细节需要注意。

#include<bits/stdc++.h>
using namespace std;
#define fuck(x) cout<<#x<<"      "<<x<<endl;
const int mod=1e8+7;
const int maxn=1e4+10;
int ans,tmp,t,n,flag,a[maxn],rec[maxn];
char str[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        memset(rec,0,sizeof(rec));
        scanf("%s",str);
        n=strlen(str);
        for(int i=0;i<n;i++)
            a[i+1]=str[i]-'0';
        for(int i=0;i<=min(2,a[1]);i++)
        {
            flag=1;
            tmp=(i==1)?2:1;
            rec[1]=i;
            for(int j=2;j<=n;j++)
            {
                int mmp=a[j-1]-rec[j-1]-((j-2!=0)?rec[j-2]:0);
                if(mmp>2||mmp<0)
                {
                    flag=0;
                    break;
                }
                if(mmp==1)
                    tmp=(tmp*2)%mod,rec[j]=1;
                else
                    if(mmp==0)
                        rec[j]=0;
                    else
                       rec[j]=2;
            }
            if(!flag)
                continue;
            if(n==1)
            {
                if(rec[1]!=a[1])
                    continue;
            }
            else
            {
                if(rec[n-1]+rec[n]!=a[n])
                    continue;
            }
            ans=(ans+tmp)%mod;
        }
        printf("%d
",ans);
    }
    return 0;
}