Description
Taring 喜欢晴天，也喜欢雨天。
Taring说：我想体验连续的(K)天的晴朗，去远足，去放歌；我还想再这(K)个晴天之后，再去体验连续的K天的云雨，去感受落雨时的轻语。这是令Taring最开心的事情了。其它的时间，Taring会在机房默默的编写着代码。
当然，Taring不想在这连续的(K)个晴天和连续的(K)个雨天里被机房的事务打扰或者被自然天气的变化中断。也就是说，这K个晴天和K个雨天必须是连续的，但是他们之间并不需要时间连续。显然的，Taring如果在感受了连续的(K)天晴朗后，前去机房写代码，等待下雨的时候再次开始他的感悟，这样是不会影响Taring的心情的。
Taring通过天气预报得到了最近连续(N)天中若干天的天气情况（天气情况只有“晴”和“雨”两种），但其他的天数的天气情况均是未知的。
他想知道有多少种可能的不同的天气情况（对于两种天气情况，如果有任意一天的天气情况是不一样的，就算做不同的天气情况），使他能够完成这两项体验。
Input Format
输入共有两行。
第(1)行有(2)个整数，分别表示上文中所述的(N)和(K)。
第2行是一个长度为N的字符串，仅包含有(B)（清），(W)（雨），(X)（未知）三种字符。
Output Format
输出一个整数(Ans)，表示合法的天气方案数量。
由于(Ans)可能很大，请将答案(Mod;1,000,000,007 (10^9+7))
Sample Input
4 2
XXXX
Sample Output
1
这题是usedtobe大佬要我做的，他的dp比我的好写，我也不知道他写了什么。
考虑最后的方案肯定时晴雨天相
我的做法是这样的(f[i][j][k])表示前(i)天，且最后一天是(j)天气((0)晴天，(1)雨天)，且状态为(k)的方案数((0)表示没有经历连续(K)个晴天，(1)表示已经经过了连续(K)个晴天，(2)表示已经经过了连续(K)个晴天和连续(K)个雨天)。
运用前缀和优化可以把复杂度优化到(O(n))，转移脑补吧。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define rhl (1000000007)
#define maxn (1000010)
int ans,N,K,f[maxn][2][3],pre[2][maxn]; char s[maxn]; //f[i][j][k]表示长度为i，最后一个是j(01),切当前状态为k的方案数
inline void upd(int &x) { if (x < 0) x += rhl; if (x >= rhl) x -= rhl; }
int main()
{
freopen("1285.in","r",stdin);
freopen("1285.out","w",stdout);
scanf("%d %d
",&N,&K); scanf("%s",s+1);
for (int i = 1;i <= N;++i)
{
if (s[i] == 'B') pre[0][i] = i;
else if (s[i] == 'W') pre[1][i] = i;
pre[0][i] = max(pre[0][i],pre[0][i-1]);
pre[1][i] = max(pre[1][i],pre[1][i-1]);
}
f[0][0][0] = f[0][1][0] = 1;
for (int i = 1,l1,l2,mx;i <= N;++i) //枚举位置
{
for (int p = 0,q = 1;p < 2;++p,q ^= 1)
{
if (p == 0&&s[i] == 'W') continue;
if (p == 1&&s[i] == 'B') continue;
l1 = i-K+1; l2 = pre[q][i]; mx = max(l1,l2);
//无长度拓展
for (int k = 0;k < 3;++k)
{
f[i][p][k] += f[i-1][q][k];
if (mx) f[i][p][k] -= f[mx-1][q][k];
upd(f[i][p][k]);
}
//有长度拓展
if (l1&&l1 >= l2)
{
//k == 0
if (p == 1)
{
f[i][p][0] += f[l1-1][q][0];
if (l2) f[i][p][0] -= f[l2-1][q][0];
upd(f[i][p][0]);
}
//k == 1
if (p == 0)
{
f[i][p][1] += f[l1-1][q][0];
if (l2) f[i][p][1] -= f[l2-1][q][0];
upd(f[i][p][1]);
f[i][p][1] += f[l1-1][q][1];
if (l2) f[i][p][1] -= f[l2-1][q][1];
upd(f[i][p][1]);
}
//k == 2
if (p == 0)
{
f[i][p][2] += f[l1-1][q][2];
if (l2) f[i][p][2] -= f[l2-1][q][2];
upd(f[i][p][2]);
}
else
{
f[i][p][2] += f[l1-1][q][1];
if (l2) f[i][p][2] -= f[l2-1][q][1];
upd(f[i][p][2]);
f[i][p][2] += f[l1-1][q][2];
if (l2) f[i][p][2] -= f[l2-1][q][2];
upd(f[i][p][2]);
}
}
}
for (int j = 0;j < 3;++j)
{
f[i][0][j] += f[i-1][0][j]; f[i][1][j] += f[i-1][1][j];
upd(f[i][0][j]); upd(f[i][1][j]);
}
}
ans = f[N][0][2]+f[N][1][2]-f[N-1][0][2]-f[N-1][1][2]; upd(ans);
printf("%d",ans);
fclose(stdin); fclose(stdout);
return 0;
}