bzoj2958: 序列染色&&3269: 序列染色

DP这种东西，考场上就只能看命了。。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int mod=1e9+;

LL f[][][];//f[i][j][k]表示第i个位置 j=0没有连续K个的B或W,j=1只有B有,j=2 BW都有  k表示放B还是W

int b[],w[];

char ss[];

int main()

{

    int n,K;

    scanf("%d%d",&n,&K);

    scanf("%s",ss+);

    for(int i=;i<=n;i++)

    {

        b[i]=b[i-];w[i]=w[i-];

             if(ss[i]=='B')b[i]++;

        else if(ss[i]=='W')w[i]++;

    }

    memset(f,,sizeof(f));f[][][]=;

    for(int i=;i<=n;i++)

    {

        if(ss[i]=='B'||ss[i]=='X')

        {

            f[i][][]=(f[i][][]+(f[i-][][]+f[i-][][])%mod)%mod;

            f[i][][]=(f[i][][]+(f[i-][][]+f[i-][][])%mod)%mod;

            f[i][][]=(f[i][][]+(f[i-][][]+f[i-][][])%mod)%mod;

        }

        if(ss[i]=='W'||ss[i]=='X')

        {

            f[i][][]=(f[i][][]+(f[i-][][]+f[i-][][])%mod)%mod;

            f[i][][]=(f[i][][]+(f[i-][][]+f[i-][][])%mod)%mod;

            f[i][][]=(f[i][][]+(f[i-][][]+f[i-][][])%mod)%mod;

        }

        if(i<K)continue;

        if((ss[i]=='B'||ss[i]=='X')&&w[i]==w[i-K])

        {

            f[i][][]=(f[i][][]+f[i-K][][])%mod;

            f[i][][]=(f[i][][]-f[i-K][][]+mod)%mod;

        }

        if((ss[i]=='W'||ss[i]=='X')&&b[i]==b[i-K])

        {

            f[i][][]=(f[i][][]+f[i-K][][])%mod;

            f[i][][]=(f[i][][]-f[i-K][][]+mod)%mod;

        }

    }

    printf("%lld\n",(f[n][][]+f[n][][])%mod);

    return ;

 }