CodeForces 1270F Awesome Substrings

https://codeforces.com/contest/1270/problem/F

给出一个01串 \(s\) ,求 \(s\) 有多少个非空子串满足,其中有至少一个'1',且'1'的数量是子串长度的约数.

\(1 \le |s| \le 200000\)

Tutorial

设 \(n=|s|\) ,设 \(pre(i)\) 表示 \(s\) 中前 \(i\) 个字符中'1'的个数.

那么一个子串 \(s[l\cdots r]\) 产生贡献的条件为

\[k(pre(r)-pre(l-1))=r-l+1 \\ r - k \cdot pre(r) = (l - 1) - k \cdot pre(l-1) \]

考虑设定某个常数 \(T\) .

对于 \(k \le T\) ,我们可以对于每个 \(k\) 枚举每个数 \(i\) 统计相同的 \(i-k \cdot pre(i)\) 个数,复杂度 \(O(nT)\)

对于 \(k>T\) ,可以得到

\[pre(r)-pre(l-1) = \dfrac {r-l+1}k \le \dfrac nT \]

也就是说子串中'1'的数量不会太多,可以枚举 \(l-1\) ,再枚举'1'的数量,相当于要计算一个区间内某个数倍数的个数.

复杂度 \(O(n \dfrac nT)\)

取 \(T=\sqrt n\) ,总复杂度 \(O(n\sqrt n)\)

Code

https://pastebin.com/hShfjtvN

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ID(a) (n-(a))
using namespace std;
template<class T> inline bool Cmax(T &x,T y) {return x<y?x=y,1:0;}
typedef long long ll;
const int maxn=200000+50;
const int maxnode=9e7;
int M; 
int n;
int cnt[maxnode];
int pos[maxn];
int sum[maxn];
char s[maxn];
int main()
{
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;++i)
	{
		sum[i]=sum[i-1];
		if(s[i]=='1')
		{
			++sum[i];
			pos[sum[i]]=i;
		}
	}
	pos[sum[n]+1]=n+1;
	M=ceil(sqrt(n));
	ll an=0;
	for(int k=1;k<=M;++k)
	{
		++cnt[ID(0)];
		for(int i=1;i<=n;++i)
		{
			int t=ID(i-k*sum[i]);
			an+=cnt[t];
			++cnt[t];
		}
		--cnt[ID(0)];
		for(int i=1;i<=n;++i)
		{
			--cnt[ID(i-k*sum[i])];
		}
	}
	for(int i=0;i<n;++i)
	{
		for(int j=1;j<=n/M&&sum[i]+j<=sum[n];++j)
		{
			int l=pos[sum[i]+j]-i;
			int r=pos[sum[i]+j+1]-i-1;
			Cmax(l,j*(M+1));
			if(l<=r)
			{
				an+=r/j-(l-1)/j;
			}
		}
	}
	printf("%lld\n",an);
	return 0;
}