[cf]Educational Codeforces Round 81 (Rated for Div. 2) B. Infinite Prefixes

前言

传送门 :

t a g : tag: tag:*1700 贡献思维 字符串 好题

题意

给定一个 n n n长度的字符串 s s s,对于字符串 t t t是 s s s的无限复制串即 t = s s s s s s t=ssssss t=ssssss

当然 s s s只含有 1 , 0 1,0 1,0; 询问 t t t的前缀中有几个 c n t 0 − c n t 1 = = x cnt_0-cnt_1 == x cnt0​−cnt1​==x

如果有无限个输出 − 1 -1 −1

思路

这种题我们考虑 0 , 1 0,1 0,1的贡献问题,我们令 0 = + 1 , 1 = − 1 0=+1,1=-1 0=+1,1=−1,然后计算一遍前缀和

• 如果 s u m [ n ] = = 0 sum[n]==0 sum[n]==0,那么就说明不管怎么复制都是 0 0 0,但是如果其子串中有 s u m [ i ] = = x sum[i]==x sum[i]==x,那么就会有无限个满足条件的
• 否者如果 s u m [ n ] ! = 0 sum[n]!=0 sum[n]!=0的话, s u m [ i ] + k ∗ s u m [ n ] = = x sum[i]+k*sum[n]==x sum[i]+k∗sum[n]==x也就是复制了 k k k次 s s s通知枚举到了 i i i位的时候正好有,当然显然我们不可能去枚举这个 k k k

因此对于第二种问题的处理,我们转化为 ( x − s u m [ i ] ) / s u m [ n ] = = k (x-sum[i])/sum[n]==k (x−sum[i])/sum[n]==k

其中 K K K必然是一个正数,所以转化为 % s u m [ n ] = = 0 \%sum[n]==0 %sum[n]==0,当然还需要保证这两个同号,因为 k k k不能为负数即 ( x − s u m [ i ] ) / s u m [ n ] > = 0 (x-sum[i])/sum[n]>=0 (x−sum[i])/sum[n]>=0

Code

const int N = 1e5+10;
int sum[N];

void solve(){
	int n,x;cin>>n>>x;
	for(int i=1;i>a;
		if(a  == '0') sum[i] = sum[i-1]+1;
		else sum[i] = sum[i-1]-1;
	}
	
	if(sum[n] == 0){
		for(int i=1;i