QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750712#9614. 分治tobie100 ✓2416ms26012kbC++142.4kb2024-11-15 15:36:102024-11-15 15:36:10

Judging History

This is the latest submission verdict.

  • [2024-11-15 15:36:10]
  • Judged
  • Verdict: 100
  • Time: 2416ms
  • Memory: 26012kb
  • [2024-11-15 15:36:10]
  • Submitted

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