QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#913501#9614. 分治liulianll40 24ms8904kbC++142.1kb2025-02-24 15:33:232025-02-24 15:33:23

Judging History

This is the latest submission verdict.

  • [2025-02-24 15:33:23]
  • Judged
  • Verdict: 40
  • Time: 24ms
  • Memory: 8904kb
  • [2025-02-24 15:33:23]
  • Submitted

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;
			ans=(ans+(g-1)*pw2[p]);
			q=lst?k-lst+1:p+1;
			for(int i=g;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: 8532kb

input:

110

output:

15

result:

ok 1 number(s): "15"

Test #2:

score: 10
Accepted
time: 3ms
memory: 8272kb

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: 8528kb

input:

111110

output:

198

result:

ok 1 number(s): "198"

Test #4:

score: 10
Accepted
time: 3ms
memory: 8532kb

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: 3ms
memory: 8536kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

412796008

result:

ok 1 number(s): "412796008"

Test #8:

score: 5
Accepted
time: 1ms
memory: 8528kb

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: 8536kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

340672883

result:

ok 1 number(s): "340672883"

Test #12:

score: 5
Accepted
time: 3ms
memory: 8536kb

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: 13ms
memory: 8580kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

468567454

result:

ok 1 number(s): "468567454"

Test #16:

score: 10
Accepted
time: 24ms
memory: 8904kb

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%