Submission #7873248


Source Code Expand

Copy
#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;
		}
		tout<<D[i];
	}
	if(check(SZ,SZ)) ret=(ret+1)%MOD;
	tout<<'\n'<<SZ<<' '<<ret<<'\n';
	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

Submission Time
Task C - Division by Two with Something
User Lawali
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1716 Byte
Status CE

Compile Error

./Main.cpp: In function ‘int solve(int)’:
./Main.cpp:42:7: error: no match for ‘operator<<’ (operand types are ‘std::istream {aka std::basic_istream<char>}’ and ‘int’)
   tout<<D[i];
       ^
./Main.cpp:42:7: note: candidate: operator<<(int, int) <built-in>
./Main.cpp:42:7: note:   no known conversion for argument 1 from ‘std::istream {aka std::basic_istream<char>}’ to ‘int’
In file included from /usr/include/c++/5/string:52:0,
                 from /usr/include/c++/5/bits/locale_classes.h:40,
                 from /usr/include/c++/5/bits/ios_base.h:41,
                 from /usr/include/c++/5/ios:42,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from /usr/include/c++/5/complex:45,
                 from /usr/include/c++/5/ccomplex:38,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52,
                 from ./Main.cpp:1:
/usr/include/c++/5/bits/basic_string.h:5257:5: note: candidate: template<class _CharT, cl...