Submission #7873285

---

Source Code Expand

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int MOD=998244353;
int N, D[200000], PS[200001], P2[200001], V[200001];
bool chk[200001];
string X;

bool check(int c, int SZ)
{
	for(int p=0;p*SZ<N;p++) {
		for(int i=0;i<c;i++) {
			if(X[p*SZ+i]<(D[i]^(p&1))+'0') return false;
			if(X[p*SZ+i]>(D[i]^(p&1))+'0') return true;
		}
		if(PS[(p+1)*SZ]-PS[p*SZ+c]<(SZ-c)*(p&1)) return false;
		if(PS[(p+1)*SZ]-PS[p*SZ+c]>(SZ-c)*(p&1)) return true;
	}
	return true;
}

int solve(int SZ)
{
	int ret=0;
	bool L=false;
	for(int i=0;i<SZ;i++) {
		D[i]=1;
		if(L || X[i]=='1' && check(i+1,SZ)) ret=(ret+P2[SZ-1-i])%MOD;
		else {
			if(X[i]=='1') L=true;
			D[i]=0;
		}
	}
	if(check(SZ,SZ)) ret=(ret+1)%MOD;
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int ans;
	cin>>N>>X;
	P2[0]=1; ans=2*N;
	for(int i=N-1;i>=0;i--) {
		if(X[i]=='1') ans=(ans+2LL*N*P2[N-1-i])%MOD;
		P2[N-i]=(2*P2[N-1-i])%MOD;
	}
	for(int i=0;i<N;i++) PS[i+1]=PS[i]+X[i]-'0';
	if(N&1) {
		chk[1]=true;
		V[1]=solve(1);
	}
	for(int i=2;i*i<=N;i++) if(N%i==0) {
		if(N/i&1) {
			chk[i]=true;
			V[i]=solve(i);
		}
		if(i*i!=N && (i&1)) {
			chk[N/i]=true;
			V[N/i]=solve(N/i);
		}
	}
	for(int i=1;i<=N;i++) if(chk[i]) {
		ans=(ans+2LL*(N-i)*(MOD-V[i]))%MOD;
		for(int j=3*i;j<=N;j+=2*i) V[j]=(V[j]+MOD-V[i])%MOD;
	}
	cout<<ans<<'\n';
	return 0;
}

Submission Info

Judge Result