解题思路
1) 反向计数：总方案 − 坏方案
- 记
X 的个数为 cntX，总方案数：2cntX。
- “坏方案”定义：最终串 没有 连续 k 个
B。
- 于是答案 = 2cntX−bad (取模)。
下面重点是线性时间统计 bad。
2) 线性 DP：禁止出现 k 连 B
记：
okB[i]：第 i 位能填/保持 B（即 s[i]=W）。okW[i]：第 i 位能填/保持 W（即 s[i]=B）。Wpre[i]：前 i 位 W 的个数（前缀和），用于 O(1) 判断某个区间是否含 W。
定义 DP：
dp[i]：前 i 位构成的合法填充数（没有 k 连 B）。g[i]：前 i 位且第 i 位为 W 的合法填充数。设边界 dp[0]=g[0]=1。
转移（i=1..n）：
-
放 W：若 okW[i]，则
g[i] = dp[i-1]，并把它计入 dp[i] += dp[i-1]。
-
放 B：若 okB[i]，先把所有在第 i 位放 B 的情况加上：add = dp[i-1]。
但若最后 k 位都可为 B（区间 [i−k+1,i] 无 W），放 B 时会产生一个以 i 结尾的 k 连 B。
此时需要剔除“前缀最后 k−1 个都是 B”的情况，其数量恰为 g[i-k]（即第 i−k 位为 W 的方案数；i-k=0 时用 g[0]=1）。
因而：
if i>=k and (Wpre[i]-Wpre[i-k]==0): add -= g[i-k]
dp[i] += add
正确性：dp[i-1] 中所有合法前缀接上 B 都尝试计入；只有在能构成“末尾恰好 k 个 B”时会违禁，这部分与“第 i−k 位为 W 且后 k−1 位全 B”一一对应，故减去 g[i-k] 即可。
注意只需 g[·] 一个量，转移为 O(1)。
3) 特判 k=1
若 k=1，好串即“存在一个 B”。
- 若原串中有固定
B，所有填充都为好串：答案 =2cntX；
- 否则“坏串”为所有位置都取
W 的唯一方案：答案 =2cntX−1。
4) 复杂度
- 预处理与 DP 皆为一次线性扫描，时间 O(n)，空间 O(1)（只用几个数组/前缀和）。
- 满足 n≤106 的限制。
代码实现
import sys
MOD = 10**9 + 7
def mod_pow2(x):
# 2^x % MOD
return pow(2, x, MOD)
def solve():
data = sys.stdin.read().strip().split()
n = int(data[0]); k = int(data[1])
s = data[2].strip()
cntX = s.count('X')
total = mod_pow2(cntX)
if k == 1:
# 只要存在一个 B 即为好串
if 'B' in s:
print(total % MOD)
else:
print((total - 1 + MOD) % MOD)
return
# 前缀 W 计数，用于判断窗口是否含 W
Wpre = [0]*(n+1)
for i, ch in enumerate(s, 1):
Wpre[i] = Wpre[i-1] + (1 if ch == 'W' else 0)
dp = [0]*(n+1)
g = [0]*(n+1) # 以 W 结尾
dp[0] = g[0] = 1
for i in range(1, n+1):
ch = s[i-1]
okB = ch != 'W'
okW = ch != 'B'
# 选 W
if okW:
g[i] = dp[i-1]
dp[i] = (dp[i] + dp[i-1]) % MOD
else:
g[i] = 0
# 选 B
if okB:
add = dp[i-1]
if i >= k and Wpre[i] - Wpre[i-k] == 0:
add -= g[i-k]
dp[i] = (dp[i] + add) % MOD
bad = dp[n] % MOD
ans = (total - bad) % MOD
print(ans)
if __name__ == "__main__":
solve()
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1'000'000'007LL;
long long pow2(long long e){
long long a = 2, r = 1;
while(e){
if(e&1) r = (r*a)%MOD;
a = (a*a)%MOD;
e >>= 1;
}
return r;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
if(!(cin >> n >> k)) return 0;
string s; cin >> s;
int cntX = 0; bool hasB=false;
for(char c: s){
if(c=='X') cntX++;
if(c=='B') hasB=true;
}
long long total = pow2(cntX);
if(k==1){
long long ans = hasB ? total : (total - 1 + MOD) % MOD;
cout << ans << "\n";
return 0;
}
// 前缀 W 数
vector<int> Wpre(n+1,0);
for(int i=1;i<=n;i++)
Wpre[i]=Wpre[i-1]+(s[i-1]=='W');
vector<long long> dp(n+1,0), g(n+1,0);
dp[0]=g[0]=1;
for(int i=1;i<=n;i++){
char ch=s[i-1];
bool okB = ch!='W';
bool okW = ch!='B';
// 选 W
if(okW){
g[i]=dp[i-1];
dp[i]=(dp[i]+dp[i-1])%MOD;
}else g[i]=0;
// 选 B
if(okB){
long long add = dp[i-1];
if(i>=k && (Wpre[i]-Wpre[i-k]==0)){
add = (add - g[i-k]) % MOD;
}
dp[i]=(dp[i]+add)%MOD;
}
}
long long bad = (dp[n]%MOD + MOD)%MOD;
long long ans = (total - bad) % MOD;
if(ans<0) ans += MOD;
cout << ans << "\n";
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static final long MOD = 1_000_000_007L;
static long pow2(long e){
long a = 2, r = 1;
while(e > 0){
if((e & 1) == 1) r = (r * a) % MOD;
a = (a * a) % MOD;
e >>= 1;
}
return r;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
String s = br.readLine().trim();
int cntX = 0; boolean hasB = false;
for(char c: s.toCharArray()){
if(c=='X') cntX++;
if(c=='B') hasB = true;
}
long total = pow2(cntX);
if(k == 1){
long ans = hasB ? total : (total - 1 + MOD) % MOD;
System.out.println(ans);
return;
}
// 前缀 W 计数
int[] Wpre = new int[n+1];
for(int i=1;i<=n;i++){
Wpre[i] = Wpre[i-1] + (s.charAt(i-1)=='W' ? 1 : 0);
}
long[] dp = new long[n+1];
long[] g = new long[n+1]; // 以 W 结尾
dp[0] = g[0] = 1;
for(int i=1;i<=n;i++){
char ch = s.charAt(i-1);
boolean okB = ch!='W';
boolean okW = ch!='B';
// 放 W
if(okW){
g[i] = dp[i-1];
dp[i] = (dp[i] + dp[i-1]) % MOD;
}else g[i]=0;
// 放 B
if(okB){
long add = dp[i-1];
if(i>=k && (Wpre[i]-Wpre[i-k]==0)){
add = (add - g[i-k]) % MOD;
}
dp[i] = (dp[i] + add) % MOD;
}
}
long bad = (dp[n]%MOD + MOD)%MOD;
long ans = (total - bad) % MOD;
if(ans < 0) ans += MOD;
System.out.println(ans);
}
}
