自动搬运

查看原文

来自洛谷，原作者为

	Hugoi 你觉得做不出来，那你就做不出来

搬运于2025-08-24 22:59:28，当前版本为作者最后更新于2024-11-15 12:12:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

好题。

为什么只有绿？

题意

给定一个长度为 $n$ 的只包含 'W','X','B' 的字符串，其中 'X' 必须变成 'W' 或 'B'。

给定 $k$,如果一个字符串中存在长为 $k$ 的都为 'W' 的连续段，并且这个连续段之前存在长为 $k$ 的都为 'B' 的连续段，那么这个字符串就是合法的。

求将所有 'X' 变成 'W' 或 'B' 后合法字符串个数。

思路

先考虑 'B' 段。

想一想怎么算不会算重。

我们只在每一个长为 $k$ 的 'B' 段第一次出现时考虑，这样就不会算重了。

于是我们设 $f_i$ 表示考虑前 $i$ 个位置，其中 $i$ 这个位置是字符串中第一个长度为 $k$ 的连续 'B' 段的结尾，这样的字符串的方案数。

怎么转移呢？

先判断 $i-k+1\sim i$ 是否可以全变成 'B'，并且要求 $i-k$ 位置不是 'B'，前 $i-k$ 个位置中不存在长为 $k$ 的 'B' 段。

于是设 $g_i$ 表示考虑前 $i$ 个位置，并且前 $i$ 个位置没有长为 $k$ 的 'B' 段的方案数。

于是 $f$ 就能从 $g$ 转移了。

如果满足上述条件并且 $i-k$ 位置为 'X'，此时这个 'X' 必须变成 'W'，那么：

$f_i=g_{i-k-1}$

否则：

$f_i=g_{i-k}$

那 $g$ 怎么算？

其实 $g$ 也可以从 $f$ 转移过来的。

我们可以算出到当前位置为止的总方案数，再减去所有合法的即可。

也就是：

$g_i=2^{prex_i}-\sum_{j=1}^{i}f_j$

前缀和优化一下即可。

但细想一下，其实这里会出问题的，本人就被卡了好久。

想明白了么？

$f_i$ 是只关心前面，不关心后面填啥的方案数，这如果直接贡献到后面的 $g_j$ 可能会算少，因为 $i\sim j$ 之间也有可能存在 'X'。

于是在算前缀和的时候多处理一下就行了。

这样对于 'B' 段的dp就做完了。

同理，对于 'W' 段从后往前做一次即可。

怎么算答案?

现在设 'B' 段的 $f$ 数组为 $f1$，'W' 段的 $f$ 数组为 $f2$。

$ans=\sum_{i=1}^{n}\sum_{j=i+1}^{n}f1_i\times f2_j\times 2^{prex_j-prex_{i-1}}$

这是 $O(n^2)$ 的，但是可优化到 $O(n)$。

枚举 $j$，记录一个 $sum$ 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,f1[N],f2[N],g1[N],g2[N],k,s1[N],s2[N],pw[N],prex[N],lstw[N],sufx[N],nxtb[N],ans;
string c;
signed main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k>>c;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
	c=' '+c;
	int lst=0;
	for(int i=1;i<=n;i++){
		if(c[i]=='W') lst=i;
		prex[i]=prex[i-1]+(c[i]=='X');
		lstw[i]=lst;
	}
	for(int i=0;i<k;i++) g1[i]=pw[prex[i]];
	for(int i=k;i<=n;i++){
		s1[i]=(s1[i-1]*(c[i]=='X'?2:1))%mod;
		if(i-lstw[i]>=k){
			if(c[i-k]!='B'){
				if(c[i-k]=='X') f1[i]=g1[i-k-1];
				else f1[i]=g1[i-k];
				(s1[i]+=f1[i])%=mod;
			}
		}
		g1[i]=(pw[prex[i]]-s1[i]+mod)%mod;
	}
	int nxt=n+1;
	for(int i=n;i>=1;i--){
		if(c[i]=='B') nxt=i;
		sufx[i]=sufx[i+1]+(c[i]=='X');
		nxtb[i]=nxt;
	}
	for(int i=n+1;i>n-k+1;i--) g2[i]=pw[sufx[i]];
	for(int i=n-k+1;i>=1;i--){
		s2[i]=s2[i+1]*(c[i]=='X'?2:1)%mod;
		if(nxtb[i]-i>=k){
			if(c[i+k]!='W'){
				if(c[i+k]=='X') f2[i]=g2[i+k+1];
				else f2[i]=g2[i+k];
				(s2[i]+=f2[i])%=mod;
			}
		}
		g2[i]=(pw[sufx[i]]-s2[i]+mod)%mod;
	}
	int sum=0;
	for(int j=1;j<=n;j++){
		(ans+=sum*f2[j]%mod)%=mod;
		(sum*=(c[j]=='X'?2:1))%=mod;
		(sum+=f1[j])%=mod;
	}
	cout<<ans<<'\n';
}