简单的平衡规划题目。
注意到“倍数”的限制，这很平衡规划。我们设限制为 $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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #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;
}
|