QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#916542#9614. 分治nullptr_qwq60 30ms11856kbC++202.8kb2025-02-26 21:10:102025-02-26 21:10:11

Judging History

This is the latest submission verdict.

  • [2025-02-26 21:10:11]
  • Judged
  • Verdict: 60
  • Time: 30ms
  • Memory: 11856kb
  • [2025-02-26 21:10:10]
  • Submitted

answer

// 私は猫です
 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) ((x)&(-(x)))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
inline int qpow(int x,ll y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod; return res; }
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
int ans;
namespace combi{
    int fac[maxn],ifac[maxn],inv[maxn],pw[maxn];
    void init(const int N){
        fac[0]=ifac[0]=inv[0]=pw[0]=1;
        F(i,1,N)fac[i]=1ll*fac[i-1]*i%mod;
        ifac[N]=qpow(fac[N],mod-2);
        dF(i,N-1,1)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
        F(i,1,N)inv[i]=1ll*ifac[i]*fac[i-1]%mod;
        F(i,1,N)pw[i]=add(pw[i-1],pw[i-1]);
    }
    inline int C(const int n,const int m){
        if(m>n||n<0||m<0) return 0;
        return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
    }
}
using namespace combi;
inline void Solve(int l,int r,int x,int y){
    chkmax(x,y);
    if(l==r)return ans+=x,void();
    const int mid=(l+r)>>1;
    Solve(l,mid,x,y+1),Solve(mid+1,r,x,1);
}
void solve(){
    string s; cin>>s;
    int cnt=0;
    for(char c:s)cnt+=(c=='1');
    if(cnt==1){
        init(maxn-3);
        int k=SZ(s)-1,ans=pw[k];
        F(i,1,k)F(j,1,(k+1)/(i+1)){
            const int t=k-i*j;
            if(t<j){
                const int val=1ll*C(t,j-1)*pw[t-j+1]%mod;
                if(j&1)inc(ans,val); else dec(ans,val);
            } else{
                const int val=add(1ll*C(t,j)*pw[t-j]%mod,1ll*C(t,j-1)*pw[t-j+1]%mod);
                if(j&1)inc(ans,val); else dec(ans,val);
            }
        }
        return cout<<ans,void();
    }
    int n=0;
    for(char c:s)n=(n<<1)+(c&1);
    Solve(1,n,1,1),cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int zsy=1;
    F(____,1,zsy)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3712kb

input:

110

output:

15

result:

ok 1 number(s): "15"

Test #2:

score: 10
Accepted
time: 1ms
memory: 3584kb

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: 0ms
memory: 3584kb

input:

111110

output:

198

result:

ok 1 number(s): "198"

Test #4:

score: 10
Accepted
time: 0ms
memory: 3712kb

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: 0ms
memory: 3712kb

input:

10100011000100111

output:

386882

result:

ok 1 number(s): "386882"

Test #6:

score: 20
Accepted
time: 0ms
memory: 3712kb

input:

111010011111010110

output:

1107742

result:

ok 1 number(s): "1107742"

Subtask #4:

score: 5
Accepted

Test #7:

score: 5
Accepted
time: 5ms
memory: 11444kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

412796008

result:

ok 1 number(s): "412796008"

Test #8:

score: 5
Accepted
time: 4ms
memory: 11620kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

818656648

result:

ok 1 number(s): "818656648"

Subtask #5:

score: 0
Memory Limit Exceeded

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #9:

score: 0
Memory Limit Exceeded

input:

10000000100000010010011110111101101110000000000001100000011000111111010011010101010000101001110110010001100110000110111101000101001111101111001010001001011101011111010000100010111100110000001101111

output:


result:


Subtask #6:

score: 5
Accepted

Dependency #4:

100%
Accepted

Test #11:

score: 5
Accepted
time: 6ms
memory: 11488kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

340672883

result:

ok 1 number(s): "340672883"

Test #12:

score: 5
Accepted
time: 5ms
memory: 11616kb

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: 17ms
memory: 11856kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

468567454

result:

ok 1 number(s): "468567454"

Test #16:

score: 10
Accepted
time: 30ms
memory: 11620kb

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:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%