BZOJ2958 序列染色（动态规划）

　　令f[i][0/1/2][0/1]表示前i位，不存在满足要求的B串和W串/存在满足要求的B串不存在W串/存在满足要求的B串和W串，第i位填的是B/W的方案数。转移时考虑连续的一段填什么。大讨论一波后瞎优化一波就成线性的了。k=1应该是要特判一下的不过数据里没有那就不管了。

　　成功的把这么短的题面都看错了一次。弱智dp写的心态爆炸。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1000010

#define P 1000000007

int n,m,a[N],pre[N][],p[],f[N][][],delta[][];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2958.in","r",stdin);

    freopen("bzoj2958.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    char c=getchar();while (c<'A'||c>'Z') c=getchar();

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

    {

        a[i]=(c=='X')?:(c=='B'?:);

        if (a[i]<) p[a[i]]=i;

        pre[i][]=p[];pre[i][]=p[];

        c=getchar();

    }

    a[]=;

    f[][][]=f[][][]=;

    delta[][]=(a[]!=),delta[][]=(a[]!=);

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

    {

        f[i][][]=delta[][],f[i][][]=delta[][],f[i][][]=delta[][];

        f[i][][]=delta[][],f[i][][]=delta[][],f[i][][]=delta[][];

        inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);

        inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);

        if (pre[i+][]<i-m+)

        {

            inc(delta[][],(P-f[i-m+][][])%P);

            inc(delta[][],f[i-m+][][]);

        }

        if (pre[i+][]<i-m+)

        {

            inc(delta[][],(P-f[i-m+][][])%P);

            inc(delta[][],f[i-m+][][]);

        }

        if (a[i+]==) delta[][]=delta[][]=delta[][]=;

        if (a[i+]==) delta[][]=delta[][]=delta[][]=;

    }

    cout<<(f[n][][]+f[n][][])%P;

    return ;

}