CF1270F Awesome Substrings

简单的平衡规划题目。

注意到“倍数”的限制，这很平衡规划。我们设限制为 $B$。若直接枚举 $k\le B$，条件为 $k(s_r-s_l)=r-l$，条件即为 $k\cdot s_l-l=k\cdot s_r-r$，开个桶记录一下，再扫一遍即可。这个做法时间复杂度为 $\mathcal{O}(nB)$。这是对于 $k$ 较小的做法。

考虑 $k>B$ 的答案，直接暴力枚举起点 $s$，将 $1$ 的点串在一起，这样对于每个 $s$ 最多会跳 $\mathcal{O}(\frac{n}{B})$ 次。过程中我们直接统计长度为 $k$ 的倍数的个数。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long 
using namespace std;
const int N=2e5+10,M=1e7+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,B;
char s[N];
int pre[N],sum[M<<1];
int ne[N];
ll ans;
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    B=sqrt(n)+1;
    s[0]='0';
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(s[i]=='1');
    for(int i=1;i<=B;i++)
    {
        memset(sum,0,sizeof(sum));
        for(int j=0;j<=n;j++)
        {
            int now=i*pre[j]-j+M;
            ans+=sum[now];
            sum[now]++;
        }
    }
    int pos=n+1;
    for(int i=n;~i;i--)
    {
        ne[i]=pos;
        if(s[i]=='1')pos=i;
    }
    for(int i=0;i<n;i++)
    {
        int l=i,r=ne[i];
        for(int j=1;j<=n/B&&j<=pre[n]-pre[i];j++)
        {
            l=ne[l],r=ne[r];
            int resl=max(l-i-1,j*B),resr=r-i-1;
            if(resl<resr)ans+=resr/j-resl/j;
        }
    }
    printf("%lld",ans);
    return 0;
}