题解：CF1295B Infinite Prefixes

yushihan123 · 2026-06-11 19:07:40 · 题解

首先我们可以定义 a_{i}=cnt0-cnt1，cnt0 表示 0 的个数，cnt1 表示 1 的个数。

可以发现，如果继续拼接s，a_{n+i}=a_{n}+a_{i}，那么拼接k个s，a_{k\times n+i}=k\times a_{n}+a_{i}，所以只要 k\times a_{n}+a_{i}=x，就会有一个前缀，也就是说 (x-a_{i}) \bmod a_{n}=0(a_{n}\ne0) 时答案就可以加一。

那么只需要枚举 a_{i}，如果满足条件就加一，但要注意如果 x>a_{i} 且 a_{n}<0 或者 x<a_{i} 且 a_{n}>0 可以直接跳过，不然可能不太好处理。

接下来考虑什么时候输出 -1，如果想要一直有前缀等于 x 的话，那么 a_{n} 一定等于 0，并且 a_{1} 到 a_{n} 中一定有一个数等于 x，如果成立输出 -1，否则输出 0。

注意如果 x=0 答案要加一，因为题目中说空串也是合法前缀。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N];
int a[N];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,x;
        scanf("%d%d",&n,&x);
        scanf("%s",s+1);
        int cnt0=0,cnt1=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='0') cnt0++;
            else cnt1++;
            a[i]=cnt0-cnt1;
        }
        int len=cnt0-cnt1,cnt=0,f=0;
        if(len==0){
            for(int i=1;i<=n;i++){
                if(a[i]==x){
                    f=1;
                    break;
                }
            }
            if(f){
                printf("-1\n");
                continue;
            }
            printf("0\n");
            continue;
        }
        for(int i=1;i<=n;i++){
            if(a[i]<x&&len<0||a[i]>x&&len>0) continue;
            if(abs(a[i]-x)%abs(len)==0) cnt++;
        }
        if(f){
            printf("-1\n");
            continue;
        }
        if(x==0) cnt++;
        printf("%d\n",cnt);
    }
    return 0;
}