QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#913511 | #9614. 分治 | liulianll | 40 | 25ms | 8900kb | C++14 | 2.2kb | 2025-02-24 15:38:32 | 2025-02-24 15:38:35 |
Judging History
answer
#include<bits/stdc++.h>
#define N 200000
#define mod 998244353
using namespace std;
char s[200010],t[200010];
int n,k,flagA,p;
long long ans,len,mx,lst,g,m,q;
long long fac[200010],invfac[200010],pw2[200010];
long long fastpow(long long x,int y){
long long ans=1;
while(y){
if(y&1) ans=(ans*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return ans;
}
long long C(long long n,long long m){
if(n<0||m<0||n<m) return 0;
return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
void Init(){
fac[0]=invfac[0]=1;
for(int i=1;i<=N;++i) fac[i]=fac[i-1]*i%mod;
invfac[N]=fastpow(fac[N],mod-2);
for(int i=N-1;i>=1;--i) invfac[i]=invfac[i+1]*(i+1)%mod;
pw2[0]=1;
for(int i=1;i<=N;++i) pw2[i]=(pw2[i-1]<<1)%mod;
return;
}
int main()
{
scanf("%s",s+1);
k=strlen(s+1);
for(int i=1;i<=k;++i){
n=((n<<1)+(s[i]=='1'))%mod;
t[i]=s[i];
}
Init();--k;
for(int i=1;i<=k;++i){
for(int j=1;k-i*j-j+1>=0;++j){
if(k-i*j-j<0){
if(j&1) ans=(ans+C(k-i*j,j-1)*pw2[k-i*j-j+1])%mod;
else ans=(ans-C(k-i*j,j-1)*pw2[k-i*j-j+1])%mod;
}
else{
if(j&1) ans=(ans+C(k-i*j,j)*pw2[k-i*j-j]+C(k-i*j,j-1)*pw2[k-i*j-j+1])%mod;
else ans=(ans-C(k-i*j,j)*pw2[k-i*j-j]-C(k-i*j,j-1)*pw2[k-i*j-j+1])%mod;
}
}
}
++k;
for(int i=k;i>=1;--i){
if(s[i]=='1'){
if(i==1) flagA=1;
else{
for(int j=i;j<=k;++j){
t[j]='1';
}
t[i]='0';
}
break;
}
}
if(flagA){
ans=(ans+n)%mod;
if(ans<0) ans+=mod;
printf("%lld\n",ans);
return 0;
}
t[1]='0';
for(int x=1;x<=k;++x){
if(t[x]=='0'){
++len;
mx=max(mx,len);
if(!lst) lst=x;
}
else{
g=max(m,len+1);
p=k-x;
q=lst?k-lst+1:p+1;
int st;
if(g==len+1) st=g,ans=(ans+(g-1)*pw2[p]);
else st=g+1,ans=(ans+(g)*pw2[p]);
for(int i=st;i<=q;++i){
for(int j=1;q-i*j-j+1>=0;++j){
if(p-i*j-j>=0){
if(j&1) ans=(ans+C(p-i*j,j)*pw2[p-i*j-j])%mod;
else ans=(ans-C(p-i*j,j)*pw2[p-i*j-j])%mod;
}
if(q-i*j-j+1>=0){
if(j&1) ans=(ans+C(q-i*j,j-1)*pw2[q-i*j-j+1])%mod;
else ans=(ans-C(q-i*j,j-1)*pw2[q-i*j-j+1])%mod;
}
}
}
len=lst=0;
}
}
ans=(ans+mx)%mod;
ans=(ans+n)%mod;
if(ans<0) ans+=mod;
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 2ms
memory: 8528kb
input:
110
output:
15
result:
ok 1 number(s): "15"
Test #2:
score: 10
Accepted
time: 3ms
memory: 8528kb
input:
101
output:
12
result:
ok 1 number(s): "12"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 2ms
memory: 8900kb
input:
111110
output:
198
result:
ok 1 number(s): "198"
Test #4:
score: 10
Accepted
time: 2ms
memory: 8528kb
input:
1001001
output:
253
result:
ok 1 number(s): "253"
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #5:
score: 0
Wrong Answer
time: 3ms
memory: 8528kb
input:
10100011000100111
output:
386594
result:
wrong answer 1st numbers differ - expected: '386882', found: '386594'
Subtask #4:
score: 5
Accepted
Test #7:
score: 5
Accepted
time: 4ms
memory: 8536kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
412796008
result:
ok 1 number(s): "412796008"
Test #8:
score: 5
Accepted
time: 3ms
memory: 8532kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
818656648
result:
ok 1 number(s): "818656648"
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 5
Accepted
Dependency #4:
100%
Accepted
Test #11:
score: 5
Accepted
time: 3ms
memory: 8532kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
340672883
result:
ok 1 number(s): "340672883"
Test #12:
score: 5
Accepted
time: 3ms
memory: 8532kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
555946758
result:
ok 1 number(s): "555946758"
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 10
Accepted
Dependency #6:
100%
Accepted
Test #15:
score: 10
Accepted
time: 15ms
memory: 8628kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
468567454
result:
ok 1 number(s): "468567454"
Test #16:
score: 10
Accepted
time: 25ms
memory: 8900kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12752860
result:
ok 1 number(s): "12752860"
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%