Contest Duration: - (local time) (150 minutes) Back to Home

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 2019-10-05 23:02:12+0900 C - Division by Two with Something Lawali C++14 (GCC 5.4.1) 0 1716 Byte 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...```