CodeForces 204D. Little Elephant and Retro Strings

//By momo
#include<cstdio>
#define N 1000010
#define M 1000000007
#define LL long long

LL n, k, ans, i; char a[N];
LL W[N], B[N], b[N], cnt;

int main(){
    scanf("%I64d%I64d%s", &n, &k, a+1);
    
    b[0] = 1; cnt = 0;
    for(i = 1; i <= n; i++){
        if(a[i] == 'W') cnt = 0;
        else cnt++;
        if(a[i] == 'X') b[i] = (b[i-1]*2)%M;
        else b[i] = b[i-1];
        
        if(cnt < k) continue;
        if(i == k) b[i] = (b[i]-1+M)%M, B[i] = 1;
        else if(a[i-k] != 'B')
            b[i] = (b[i]-b[i-k-1]+M)%M, B[i] = b[i-k-1];
    }
    
    b[n+1] = 1; cnt = 0;
    for(i = n; i >= 1; i--){
        if(a[i] == 'B') cnt = 0;
        else cnt++;
        if(a[i] == 'X') b[i] = (b[i+1]*2)%M, W[i] = (W[i+1]*2)%M;
        else b[i] = b[i+1], W[i] = W[i+1];

        if(cnt < k) continue;
        if(i == n-k+1) b[i] = (b[i]-1+M)%M, W[i] = 1;
        else if(a[i+k] != 'W')
            b[i] = (b[i]-b[i+k+1]+M)%M, W[i] = (W[i]+b[i+k+1])%M;
    }
    for(i = 1; i <= n; i++) ans = (ans+B[i]*W[i+1]%M)%M;
    printf("%I64d\n", ans);
}

This problem is way complicated than I expected it.After I finish reading the problem, something comes to my mind.

I can do the left half of it then do the right one,

so I then wrote something idiotic that has many same combination in it. I try to fix the problem, but suddenly found out I am STUCK. After eating my lunch, I finally figure it out.

And here comes the solution...

First, I'll do the left part of it, which is the Bs.

To cross out the repeated combination, the thing I keep track of ( B[i] ) is a set of combination that end at point i, with no other k consecutive Bs on its left. b[i] does the job of subtracting the combination with other k consecutive Bs, and B[i] is the thing we need.

Second, I'll use the same method to find the right part of it, which is the Ws.

But we can have more freedom on the right side( you can choose which side you want to give more freedom to, but there should only be one side. )

For example:

k = 3 ( O means optional. )

OOOWBBB | WWWOOOO
OOOWBBB | OOOWWWO
OOOWBBB | OWWWOOO

the left side must be WBBB, but the right side has more freedom, you can choose which position you want to put 3Ws in. But if you give freedom to both side, sth terrible will happen:

Take another example,

k = 3

WWWBBB   B | WWWWWWW
WWWBBB | B   WWWWWWW

they are the same but will be counted twice.
Be careful and you can easily accept this problem.