QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#913766 | #9614. 分治 | liulianll | 0 | 0ms | 0kb | C++14 | 2.6kb | 2025-02-24 18:38:34 | 2025-02-24 18:38:36 |
Judging History
answer
#include<bits/stdc++.h>
#define N 200000
#define B 450
#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 F[452][200010],G[452][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;
for(int i=1;i<=B;++i){
for(int t=i+1;t<=N;++t){
F[i][t]=(2ll*F[i][t-1]-F[i][t-i-1]+pw2[t-i-1])%mod;
if(F[i][t]<0) F[i][t]+=mod;
}
}
for(int j=1;j<=B;++j){
for(int t=j+1;t<=N;++t){
if(j&1) G[j][t]=(G[j][t-j]+C(t-j,j)*pw2[t-2*j])%mod;
else G[j][t]=(G[j][t-j]-C(t-j,j)*pw2[t-2*j])%mod;
if(G[j][t]<0) G[j][t]+=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;ans=n;
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%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(mx,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<=B;++i){
ans=(ans+F[i][p])%mod;
}
for(int j=1;j<=B;++j){
if(p-B*j-g*j+j<0) continue;
ans=(ans+G[j][p-B*j-g*j+j])%mod;
}
for(int i=st;i<=q;++i){
for(int j=1;q-i*j-j+1>=0;++j){
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;
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: 0
Memory Limit Exceeded
Test #1:
score: 0
Memory Limit Exceeded
input:
110
output:
15
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Memory Limit Exceeded
Test #7:
score: 0
Memory Limit Exceeded
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
412796008
result:
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%