Infinite Prefixes （Codeforces- P1295B）
一、 题目大意
给你一个长度为 n 的二进制字符串 s（只包含 0 和 1）。 你要构造一个无限长的字符串 t，它是由 s 无限次拼接得到的（t=sssss…）。 定义一个字符串的“平衡值”为：字符 '0' 的数量减去字符 '1' 的数量。 现在问你：在无限长字符串 t 的所有前缀中，有多少个前缀的平衡值恰好等于 x？ 如果数量有无限个，输出-1。(注：空字符串也算前缀，其平衡值为 0)
数据范围：1≤n≤10^5，。
二、 思考过程（为什么不是单调队列？）
很多同学一看到“前缀”和“平衡值”，第一反应是：能不能用滑动窗口？能不能用单调栈维护最值？绝对不行。
单调队列/栈解决的是“局部视野内的相对最值”问题（比如谁挡住了谁，谁是区间最大值）。 而这道题是在一个无限延伸的序列上，找一个绝对等于 x的值。无限循环的物理模型，本质上就是“等差数列求通项公式”。这道题是一道披着字符串外衣的数学周期枚举题。
三、 题目分析与解题思路
我们将单个字符串 s 的前缀平衡值预处理出来，记为 a[i]。 那么，完整走完一圈 s 所带来的总平衡值变化量就是 a[n]。
对于无限循环字符串 t 的任意一个前缀，它一定可以拆解为：k 个完整的 s 周期 + 内部多出来的 i 个字符（其中 k≥0，1≤i≤n）。
此时，这个前缀的总平衡值公式为：
总平衡值=k⋅a[n]+a[i]
题目要求这个总平衡值等于 x，我们列出一元一次方程：
k⋅a[n]+a[i]=x
移项解得我们需要找的周期数 k：
k=a[n]x−a[i]
解题核心：既然 a[n] 是定值，目标 x 也是定值。我们只需要用一个for循环遍历单圈内部的所有位置 i，看看在这个位置上，能不能解出一个合法的整数 k。
由于方程里 a[n] 在分母的位置，所以我们必须极其严谨地分两种情况讨论：
情况一：a[n]==0（转圈不改变平衡值）
如果一整圈的平衡值是 0，说明不管经历多少个周期，平衡值永远在原地踏步。 此时方程变为 0=x−a[i]。
如果在第一圈里找到了 a[i]==x，那么以后每一圈走到这个位置都是 x，答案是无限个，输出
-1。如果第一圈没找到，那以后永远也找不到，答案是
0。
情况二：a[n]!=0（每次转圈都有稳定的增减）
我们需要验证解出来的 k 是否合法，必须同时满足两个数学条件：
能整除：(x−a[i])(%a[n])==0。
时间不能倒流（圈数非负）：(x−a[i])/a[n]≥0。
满足这两个条件，说明在未来的第 k 圈的第 i 个位置，总平衡值刚好为 x，计数器+1。
四、 易错点总结
除零异常：在对 a[n] 取模或除法之前，必须强制把
a[n]==0的情况用if-else隔离开。空字符串陷阱：题目明确说明“空字符串也算一个有效前缀”。空串的平衡值为 0。所以在计算情况二时，如果 x==0，必须让答案初始值
cnt++。推导符号错位：很多同学把非负条件错写成
x*a[n]>=0，这是极其致命的数学错误。必须老老实实写完整的等式判断(x - a[i]) / a[n] >= 0。提前漏算补丁：在 a[n]==0 且没找到目标值时，一定要记得输出
0，否则程序什么都不输出就进入下一轮，导致输出行数对不上。
五、 时空复杂度分析
时间复杂度：O(N)。只需预处理一遍前缀和，再遍历一遍 0 到 n−1，每次判断是 O(1) 的数学取模运算。整体严格线性。
空间复杂度：O(N)。只需要一个大小为 105 的数组存储单圈的前缀平衡值。
六、 完整代码
// Infinite Prefixes cf-1295B #include <iostream> #include <cstring> using namespace std; int t; int a[100010];//a[i]代表字符串s第i个位置的平衡值 int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>t; //总共t组测试数据 while(t--){ int cnt=0;//满足条件的前缀数量 int n,x;//字符串s的长度和目标平衡值 cin>>n>>x; //初始化a数组为0 memset(a,0,sizeof(a)); string s; cin>>s; //计算单个周期字符串s的平衡值 for(int i=1;i<=s.size();i++){ //0每出现一次平衡值+1 if(s[i-1]=='0') a[i]=a[i-1]+1; //1每出现一次平衡值-1 else a[i]=a[i-1]-1; } //计算会不会有无限个：无限个的情况只能是每组字符串s的平衡值为0 //然后字符串s中存在某个位置的平衡值和x相等 if(a[n]==0){//每组字符串s的平衡值 bool flag=0;//标记s中是否存在某个位置平衡值和x相等 for(int i=1;i<=s.size();i++){//遍历s if(a[i]==x) flag=1; } if(flag==1){//如果存在就输出-1 代表有无限个 然后下一轮测试数据 cout<<"-1"<<endl; continue; } //不存在就代表根本没有 cout<<0<<"\n"; } else{ //如果要求平衡值是0 则所有字符串初始就存在一个满足条件的前缀-空串 if(x==0) cnt++; //否则就非无限个的情况 //a[n]就是每组字符串s总的平衡值 for(int i=1;i<=s.size();i++){ //如果x能被a[i]通过加多组前缀的总和得到 数量就加一 // 1. (x-a[i])%a[n]==0 保证能被完整周期整除 // 2. (x-a[i])/a[n]>=0 保证走过的圈数非负 if((x-a[i])%a[n]==0&&(x-a[i])/a[n]>=0) cnt++; } cout<<cnt<<"\n"; } } return 0; }