QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#913766#9614. 分治liulianll0 0ms0kbC++142.6kb2025-02-24 18:38:342025-02-24 18:38:36

Judging History

This is the latest submission verdict.

  • [2025-02-24 18:38:36]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-24 18:38:34]
  • Submitted

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%