视频加载失败

DD的P 1

1398 字
7 分钟
DD的P 1

题目描述#

给定一个长度为 nn 的字符串 ss,其中每个字符均为 0、1、? 之一。你需要将每个 ? 替换为 0 或 1。

给定两个整数 L,RL,R,请计算有多少种替换方案,使替换后所有极长同字符段的长度均在区间 [L,R][L,R] 内。由于答案可能很大,请将答案对 998244353998244353 取模后输出。

我们认为两种方案不同,当且仅当替换后得到的字符串不同。

名词解释#

极长同字符段:字符串中一段连续且全部相同的字符,并且不能向左或向右再扩展一个字符而保持全部相同。

例如,字符串 0011100 的极长同字符段为:

00、111、00

它们的长度分别为 2,3,22,3,2。

输入描述#

每个测试文件均包含多组测试数据。

第一行输入一个整数 TT(1≤T≤1041\le T\le 10^4),表示数据组数。每组测试数据描述如下:

第一行输入三个整数 n,L,Rn,L,R(1≤L≤R≤n≤2×1051\le L\le R\le n\le 2\times 10^5),表示字符串长度、极长同字符段长度下限和长度上限。

第二行输入一个长度为 nn 的字符串 ss,其中每个字符均为 0、1、? 之一。

除此之外,保证单个测试文件中所有测试数据的 nn 之和不超过 2×1052\times 10^5。

输出描述#

对于每组测试数据,新起一行。

输出一个整数,表示满足条件的替换方案数对 998244353998244353 取模后的结果。

示例 1#

输入#

6
1 1 1
0
1 1 1
?
3 1 2
000
5 2 3
0???1
6 1 6
??????
10 1 5
0?11?????1

输出#

1
2
0
2
64
58

我的代码#

#include <bits/stdc++.h>
using namespace std;
int MOD = 998244353;
int main ()
{
int t;
cin>>t;
while(t--)
{
int n,l,r;
cin>>n>>l>>r;
vector <char> a(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
vector <vector <int> > f (n+1,vector <int> (2));
f[0][0]=1;
f[0][1]=1;
int last1=0;
int last0=0;
vector <int> pre1 (n+1);
vector <int> pre0 (n+1);
pre1[0]=f[0][1];
pre0[0]=f[0][0];
for(int i=1;i<=n;i++)
{
if(a[i]=='1')
{
last1=i;
}
if(a[i]=='0')
{
last0=i;
}
int tL=max((i-r),0);
int rig=i-l;
int L1=max(tL,last0);
int L0=max(tL,last1);
if(L1<=rig)
{
f[i][1]=pre0[rig];
if(L1>0)
{
f[i][1]-=pre0[L1-1];
}
if (f[i][1] < 0) {
f[i][1] += MOD;
}
}
if(L0<=rig)
{
f[i][0]=pre1[rig];
if(L0>0)
{
f[i][0]-=pre1[L0-1];
}
if (f[i][0] < 0) {
f[i][0] += MOD;
}
}
pre0[i] = (pre0[i - 1] + f[i][0])%MOD;
pre1[i] = (pre1[i - 1] + f[i][1])%MOD;
}
cout << (f[n][0] + f[n][1]) % MOD << '\n';
}
}
# 题解:区间长度限制下的字符串替换
## 1. 状态定义
设:
```cpp
f[i][0]

表示前 i 个字符合法,并且最后一个极长同字符段由 0 组成的方案数。

同理:

f[i][1]

表示最后一个极长同字符段由 1 组成的方案数。

为了统一处理第一段,初始化:

f[0][0] = 1;
f[0][1] = 1;

这里的 0 表示空前缀。


2. 枚举最后一段#

假设前 i 个字符的最后一段从 p+1 开始,那么:

前缀:1...p
最后一段:p+1...i

最后一段长度为:

i - p

题目要求每段长度在 [l,r] 内,因此:

l <= i-p <= r

变形得到:

i-r <= p <= i-l

代码中:

int tL = max(i - r, 0);
int rig = i - l;

其中:

  • tL 是 p 的基本左边界;
  • rig 是 p 的右边界。

3. 处理固定字符和 ?#

最后一段是 1#

最后一段中不能出现固定的 0。

last0 表示当前位置之前最近的固定 0 的位置,因此必须满足:

p >= last0

所以真正的左边界是:

int L1 = max(tL, last0);

前缀最后一段必须是 0,因此:

f[i][1] = sum(f[p][0])

代码为:

if (L1 <= rig) {
f[i][1] = pre0[rig];
if (L1 > 0) {
f[i][1] -= pre0[L1 - 1];
}
if (f[i][1] < 0) {
f[i][1] += MOD;
}
}

最后一段是 0#

同理,最后一段中不能出现固定的 1。

last1 表示最近的固定 1 的位置,因此:

int L0 = max(tL, last1);

前缀最后一段必须是 1,所以:

f[i][0] = sum(f[p][1])

代码为:

if (L0 <= rig) {
f[i][0] = pre1[rig];
if (L0 > 0) {
f[i][0] -= pre1[L0 - 1];
}
if (f[i][0] < 0) {
f[i][0] += MOD;
}
}

4. 为什么前一段必须是相反字符?#

例如最后一段是 1:

... 000 | 111 ...

前一段必须以 0 结尾。

如果前一段也是 1:

... 111 | 111 ...

两段实际上应该合并成一个更长的极长段,这样划分就是错误的。

因此:

  • 最后一段是 1 时,前缀使用 f[p][0];
  • 最后一段是 0 时,前缀使用 f[p][1]。

5. 前缀和优化#

直接计算:

f[L] + f[L+1] + ... + f[R]

需要枚举区间内所有位置,复杂度较高。

因此定义:

pre0[i] = f[0][0] + f[1][0] + ... + f[i][0]
pre1[i] = f[0][1] + f[1][1] + ... + f[i][1]

例如:

f[L][0] + ... + f[rig][0]

可以通过:

pre0[rig] - pre0[L-1]

在 O(1) 时间内计算。

每次计算完 f[i][0] 和 f[i][1] 后,更新前缀和:

pre0[i] = (pre0[i - 1] + f[i][0]) % MOD;
pre1[i] = (pre1[i - 1] + f[i][1]) % MOD;

6. 正确性说明#

对于任意一个合法字符串,它的最后一个极长同字符段是唯一的。

设这段从 p+1 开始,则:

  1. p 必须满足最后一段长度在 [l,r] 内;
  2. 最后一段中不能出现与目标字符相反的固定字符;
  3. 前缀 1...p 必须已经合法;
  4. 前缀的最后一段必须是相反字符。

代码中的转移恰好枚举了所有满足这些条件的 p,因此每个合法方案都会被计算一次,并且不会被重复计算。

最终答案为:

f[n][0] + f[n][1]

因为完整字符串的最后一段只能是 0 或 1。


7. 复杂度分析#

每个位置只计算两种状态,并且每次转移使用前缀和完成。

时间复杂度:O(n)
空间复杂度:O(n)

对于所有测试数据,总复杂度为:

O(所有测试数据的 n 之和)

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

DD的P 1
https://www.xiaobaibai454.top/posts/study-26-11-15/
作者
Xiao_baibai
发布于
2026-11-15
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录