DD的P 1
题目描述
给定一个长度为 的字符串 ,其中每个字符均为 0、1、? 之一。你需要将每个 ? 替换为 0 或 1。
给定两个整数 ,请计算有多少种替换方案,使替换后所有极长同字符段的长度均在区间 内。由于答案可能很大,请将答案对 取模后输出。
我们认为两种方案不同,当且仅当替换后得到的字符串不同。
名词解释
极长同字符段:字符串中一段连续且全部相同的字符,并且不能向左或向右再扩展一个字符而保持全部相同。
例如,字符串 0011100 的极长同字符段为:
00、111、00它们的长度分别为 。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 (),表示数据组数。每组测试数据描述如下:
第一行输入三个整数 (),表示字符串长度、极长同字符段长度下限和长度上限。
第二行输入一个长度为 的字符串 ,其中每个字符均为 0、1、? 之一。
除此之外,保证单个测试文件中所有测试数据的 之和不超过 。
输出描述
对于每组测试数据,新起一行。
输出一个整数,表示满足条件的替换方案数对 取模后的结果。
示例 1
输入
61 1 101 1 1?3 1 20005 2 30???16 1 6??????10 1 50?11?????1输出
12026458我的代码
#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. 状态定义
设:
```cppf[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 开始,则:
p必须满足最后一段长度在[l,r]内;- 最后一段中不能出现与目标字符相反的固定字符;
- 前缀
1...p必须已经合法; - 前缀的最后一段必须是相反字符。
代码中的转移恰好枚举了所有满足这些条件的 p,因此每个合法方案都会被计算一次,并且不会被重复计算。
最终答案为:
f[n][0] + f[n][1]因为完整字符串的最后一段只能是 0 或 1。
7. 复杂度分析
每个位置只计算两种状态,并且每次转移使用前缀和完成。
时间复杂度:O(n)空间复杂度:O(n)对于所有测试数据,总复杂度为:
O(所有测试数据的 n 之和)文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




