QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750712 | #9614. 分治 | tobie | 100 ✓ | 2416ms | 26012kb | C++14 | 2.4kb | 2024-11-15 15:36:10 | 2024-11-15 15:36:10 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
const int mod=998244353;
const int N=2e5+9,M=5e5+9,B=450;
int cf[M];
int fac[M],inv[M],ifac[M];
void ycl(int lim=5e5)
{
cf[0]=1;cf[1]=2;
fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=1;
for(int i=2;i<=lim;i++)
{
fac[i]=fac[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ifac[i]=ifac[i-1]*inv[i]%mod;
cf[i]=cf[i-1]*2%mod;
}
}
inline int ksm(int x,int y){int z=1;for(;y;x=x*x%mod,y>>=1) if(y&1) z=z*x%mod;return z;}
inline int C(int x,int y){return x>=y&&y>=0?fac[x]*ifac[y]%mod*ifac[x-y]%mod:0;}
inline int cf2(int x){return x>=0?cf[x]:0;}
int js(int n)
{
int res=0;
for(int j=1;j<=n;j++)
for(int k=1;k<=n/j;k++)
{
res+=C(n-j*k,k)*cf2(n-j*k-k)%mod*((k&1)?1:mod-1)%mod;
res+=C(n-j*k,k-1)*cf2(n-j*k-k+1)%mod*((k&1)?1:mod-1)%mod;
res%=mod;
}
return res;
}
char s[N];
int n,ans=0;
int f[N<<1],g[N<<1];
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
ycl();
int num=0;
for(int i=1;i<=n;i++) num=(num*2+(s[i]-'0'))%mod;
ans=(js(n-1)+num)%mod;
cerr<<ans<<endl;
for(int k=1;k<=B;k++)
{
for(int i=0;i<=n;i++)
if(i<k) f[i]=g[i]=0;
else
{
f[i]=(f[i-k]+C(i-k,k)*cf2(i-k-k)%mod)%mod;
g[i]=(g[i-k]+C(i-k,k-1)*cf2(i-k-k+1)%mod)%mod;
}
int mxlen=0,hzlen=0;
for(int i=1;i<=n;i++)
{
if(i>1&&s[i]=='1')
{
int len=hzlen+1;
int mx=max(mxlen,len);
if(k==1) (ans+=mx*cf[n-i]%mod)%=mod;
if(n-i-max(mx,B)*k>=0) (ans+=f[n-i-max(mx,B)*k]*((k&1)?1:(mod-1))%mod)%=mod;
if(n-i+len-max(mx,B)*k>=0) (ans+=g[n-i+len-max(mx,B)*k]*((k&1)?1:(mod-1))%mod)%=mod;
}
if(i==1) hzlen++,mxlen=max(mxlen,hzlen);
else
{
if(s[i]=='1') hzlen=0;
else hzlen++,mxlen=max(mxlen,hzlen);
}
}
}
cerr<<ans<<endl;
for(int j=1;j<=B;j++)
{
for(int i=1;i<=n;i++)
if(i<=j) f[i]=0,g[i]=(i==j);
else
{
f[i]=(f[i-1]*2+mod-f[i-j-1]+cf2(i-j-1))%mod;
g[i]=(g[i-1]*2+mod-g[i-j-1])%mod;
}
int mxlen=0,hzlen=0;
for(int i=1;i<=n;i++)
{
if(i>1&&s[i]=='1')
{
int len=hzlen+1;
int mx=max(mxlen,len);
if(j>mx)
{
if(n-i>=0) (ans+=f[n-i])%=mod;
if(n-i+len>=0) (ans+=g[n-i+len])%=mod;
}
}
if(i==1) hzlen++,mxlen=max(mxlen,hzlen);
else
{
if(s[i]=='1') hzlen=0;
else hzlen++,mxlen=max(mxlen,hzlen);
}
}
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 8ms
memory: 22508kb
input:
110
output:
15
result:
ok 1 number(s): "15"
Test #2:
score: 10
Accepted
time: 4ms
memory: 22148kb
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: 7ms
memory: 22000kb
input:
111110
output:
198
result:
ok 1 number(s): "198"
Test #4:
score: 10
Accepted
time: 3ms
memory: 22496kb
input:
1001001
output:
253
result:
ok 1 number(s): "253"
Subtask #3:
score: 20
Accepted
Dependency #2:
100%
Accepted
Test #5:
score: 20
Accepted
time: 6ms
memory: 22072kb
input:
10100011000100111
output:
386882
result:
ok 1 number(s): "386882"
Test #6:
score: 20
Accepted
time: 8ms
memory: 22280kb
input:
111010011111010110
output:
1107742
result:
ok 1 number(s): "1107742"
Subtask #4:
score: 5
Accepted
Test #7:
score: 5
Accepted
time: 3ms
memory: 23188kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
412796008
result:
ok 1 number(s): "412796008"
Test #8:
score: 5
Accepted
time: 6ms
memory: 22840kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
output:
818656648
result:
ok 1 number(s): "818656648"
Subtask #5:
score: 5
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #9:
score: 5
Accepted
time: 4ms
memory: 22444kb
input:
10000000100000010010011110111101101110000000000001100000011000111111010011010101010000101001110110010001100110000110111101000101001111101111001010001001011101011111010000100010111100110000001101111
output:
703266161
result:
ok 1 number(s): "703266161"
Test #10:
score: 5
Accepted
time: 3ms
memory: 21728kb
input:
110100000100001000101000010010101000110111101010110000101001001100100111000011100101110110010000001111010011101001111110110010001110011101001111010101100100010011101010101111111111010110001100100110
output:
330527406
result:
ok 1 number(s): "330527406"
Subtask #6:
score: 5
Accepted
Dependency #4:
100%
Accepted
Test #11:
score: 5
Accepted
time: 9ms
memory: 22480kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
340672883
result:
ok 1 number(s): "340672883"
Test #12:
score: 5
Accepted
time: 15ms
memory: 22212kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
555946758
result:
ok 1 number(s): "555946758"
Subtask #7:
score: 10
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #13:
score: 10
Accepted
time: 23ms
memory: 23080kb
input:
110011100110101000000110101010111111001101101011010110100100110010111110110110000111011001110000101111110111011111000110001011011011101100001100100011010010111111010110010000101001001000100001100100000001000111110100000101001011100001100011011110110101101111110011100111001010001010001111001110111100...
output:
324123594
result:
ok 1 number(s): "324123594"
Test #14:
score: 10
Accepted
time: 23ms
memory: 22200kb
input:
110100110100110110001011100000011010000010000101100100001101100100110000101000111001111100001110001001101010110010111101000100111010001011001110101010001101111010000011000010110011000011100101110100000001011100111000101111010100001101011010100101110000010001101001000100111001101101110000101101011011...
output:
209285599
result:
ok 1 number(s): "209285599"
Subtask #8:
score: 10
Accepted
Dependency #6:
100%
Accepted
Test #15:
score: 10
Accepted
time: 890ms
memory: 23924kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
468567454
result:
ok 1 number(s): "468567454"
Test #16:
score: 10
Accepted
time: 1489ms
memory: 26012kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12752860
result:
ok 1 number(s): "12752860"
Subtask #9:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Dependency #8:
100%
Accepted
Test #17:
score: 25
Accepted
time: 2411ms
memory: 25888kb
input:
101100010100101011010110001111101101001010000111001111000100110110010111101100011011011111010110000000011110000010100110111110110001101001101101001110101110011000010100100101000011000010000101011001011011000000100111011110100010000100001101011110100101110000100011000101100000111111100110000111010000...
output:
711712397
result:
ok 1 number(s): "711712397"
Test #18:
score: 25
Accepted
time: 2416ms
memory: 25948kb
input:
110101110100100010101100000110000110101101111100110011100111111110000101111001101001111000110111100111110111010001000010111111110000001001011110101110001011010010010011101000110110000110110101000100111000100110101111011101111101000010000101001001000010011011000011001100111111011000111000010000100111...
output:
171668334
result:
ok 1 number(s): "171668334"
Test #19:
score: 25
Accepted
time: 1564ms
memory: 25980kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
397846555
result:
ok 1 number(s): "397846555"
Test #20:
score: 25
Accepted
time: 1599ms
memory: 25840kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
592103795
result:
ok 1 number(s): "592103795"
Extra Test:
score: 0
Extra Test Passed