QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#295909#4903. 细菌SoyTony90 1617ms16864kbC++144.5kb2024-01-01 14:51:322024-01-01 14:51:32

Judging History

你现在查看的是最新测评结果

  • [2024-01-01 14:51:32]
  • 评测
  • 测评结果:90
  • 用时:1617ms
  • 内存:16864kb
  • [2024-01-01 14:51:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int maxn=(1<<18)+10;
const int B=800;
const int lim=24e4;
const int mod=998244353;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}

int fact[maxn],inv_fact[maxn];
inline int C(int N,int M){
    if(M<0) return 0;
    if(N<M) return 0;
    return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}

int rev[maxn];
int base,w[maxn];
struct Poly{
    const static int g=3;
    int deg;
    vector<ull> f;
    ull &operator[](const int &i){return f[i];}
    ull operator[](const int &i)const{return f[i];}
    inline void set(int L){deg=L;f.resize(L);}
    inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
    inline void output(int L){for(int i=0;i<L;++i)printf("%llu ",f[i]);printf("\n");}
    inline void NTT(int L,bool type){
        set(L);
        for(int i=1;i<L;++i){
            rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
        for(int d=1;d<L;d<<=1){
            base=q_pow(type?g:q_pow(g,mod-2,mod),(mod-1)/(2*d),mod);
            w[0]=1;
            for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
            for(int i=0;i<L;i+=d<<1){
                for(int j=0;j<d;++j){
                    ull x=f[i+j],y=f[i+d+j]*w[j]%mod;
                    f[i+j]=x+y,f[i+d+j]=x-y+mod;
                }
            }
        }
        for(int i=0;i<L;++i) f[i]%=mod;
        if(!type){
            int inv_L=q_pow(L,mod-2,mod);
            for(int i=0;i<L;++i) f[i]=f[i]*inv_L%mod;
        }
    }
}F,G,H;

inline void calc(int t,int R,vector<int> &f,int coef){
    // cerr<<"calc t:"<<t<<" R:"<<R<<" coef:"<<coef<<endl;
    if(R<0) return;
    int S1=1,S2=0;
    for(int i=1;i<=t;++i){
        S1=(2ll*S1-C(i-1,(i-1+R)/2)+mod)%mod;
        S2=(2ll*S2-C(i-1,i/2-1)+mod)%mod;
        if(!((i+R)&1)) S1=(S1+C(i,(i+R)/2))%mod;
        if(i&1) S2=(S2+C(i,(i+1)/2-1))%mod;
        // cerr<<"i:"<<i<<" S1:"<<S1<<" S2:"<<S2<<endl;
        f[i]=(f[i]+1ll*coef*(S1-S2+mod)%mod+mod)%mod;
    }
}
int dp[2][maxn];
inline void solve(int t,int n,int a,vector<int> &f){
    f.push_back(1);
    if(n<=B){
        for(int i=1;i<=n;++i) dp[0][i]=dp[1][i]=0;
        dp[0][a]=1;
        for(int i=1;i<=t;++i){
            for(int j=1;j<=n;++j){
                if(j>1) dp[i&1][j-1]=(dp[i&1][j-1]+dp[i&1^1][j])%mod;
                if(j<n) dp[i&1][j+1]=(dp[i&1][j+1]+dp[i&1^1][j])%mod;
            }
            int sum=0;
            for(int j=1;j<=n;++j){
                sum=(sum+dp[i&1][j])%mod;
                dp[i&1^1][j]=0;
            }
            sum=1ll*sum*inv_fact[i]%mod;
            f.push_back(sum);
        }
    }
    else{
        for(int i=1;i<=t;++i) f.push_back(0);
        for(int i=-((t-1)/n+1)-1;i<=(t-1)/n+1;++i){
            int l=i*(n+1)+1,r=(i+1)*(n+1)-1,L,R;
            // cerr<<"i:"<<i<<" ["<<l<<","<<r<<"]"<<endl;
            if(!i){
                L=0,R=r-a;
                calc(t,R,f,1);
                L=1,R=a-l;
                calc(t,R,f,1);
                calc(t,L-1,f,-1);
            }
            else if(i>0){
                L=l-a,R=r-a;
                calc(t,R,f,(i&1)?-1:1);
                calc(t,L-1,f,(i&1)?1:-1);
            }
            else{
                L=a-r,R=a-l;
                calc(t,R,f,((-i)&1)?-1:1);
                calc(t,L-1,f,((-i)&1)?1:-1);
            }
        }
        for(int i=1;i<=t;++i) f[i]=1ll*f[i]*inv_fact[i]%mod;
    }
}

int t,n,m,k,a,b,c;
vector<int> f,g,h;
int ans;

int main(){
    fact[0]=1;
    for(int i=1;i<=lim;++i) fact[i]=1ll*fact[i-1]*i%mod;
    inv_fact[0]=1,inv_fact[lim]=q_pow(fact[lim],mod-2,mod);
    for(int i=lim-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
    t=read(),n=read(),m=read(),k=read(),a=read(),b=read(),c=read();
    solve(t,n,a,f);
    solve(t,m,b,g);
    solve(t,k,c,h);
    int L=1;
    while(L<2*t) L<<=1;
    F.set(L),G.set(L),H.set(L);
    for(int i=0;i<=t;++i) F[i]=f[i],G[i]=g[i];
    F.NTT(L,1),G.NTT(L,1);
    for(int i=0;i<L;++i) H[i]=1ll*F[i]*G[i]%mod;
    H.NTT(L,0);
    for(int i=0;i<=t;++i) ans=(ans+1ll*H[i]*h[t-i])%mod;
    ans=1ll*ans*fact[t]%mod;
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 3ms
memory: 7904kb

input:

50 49 44 48 49 15 25

output:

544847893

result:

ok 1 number(s): "544847893"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 10
Accepted
time: 7ms
memory: 8680kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 7ms
memory: 9948kb

input:

5000 4994 4997 4994 4399 1826 1332

output:

65414465

result:

ok 1 number(s): "65414465"

Subtask #3:

score: 15
Accepted

Test #5:

score: 15
Accepted
time: 206ms
memory: 15260kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 825ms
memory: 16492kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 44ms
memory: 15964kb

input:

120000 119999 1 1 19896 1 1

output:

68846585

result:

ok 1 number(s): "68846585"

Subtask #4:

score: 10
Accepted

Test #8:

score: 10
Accepted
time: 51ms
memory: 15312kb

input:

119000 119991 119991 1 23819 52139 1

output:

944500934

result:

ok 1 number(s): "944500934"

Subtask #5:

score: 15
Accepted

Dependency #4:

100%
Accepted

Test #9:

score: 15
Accepted
time: 152ms
memory: 15560kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 152ms
memory: 15336kb

input:

120000 13997 13997 1 9768 6131 1

output:

151873213

result:

ok 1 number(s): "151873213"

Subtask #6:

score: 35
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #11:

score: 35
Accepted
time: 389ms
memory: 15240kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 507ms
memory: 15920kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 632ms
memory: 16704kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 755ms
memory: 16000kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 873ms
memory: 16000kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 1002ms
memory: 16528kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 1617ms
memory: 16180kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 832ms
memory: 16864kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 360ms
memory: 15508kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 204ms
memory: 15928kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 73ms
memory: 15788kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 59ms
memory: 15744kb

input:

120000 119996 119994 1 58014 49559 1

output:

682979057

result:

ok 1 number(s): "682979057"

Subtask #7:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #23:

score: 10
Accepted
time: 561ms
memory: 16152kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 751ms
memory: 16560kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 955ms
memory: 15568kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 1123ms
memory: 16092kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 1316ms
memory: 15968kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 1506ms
memory: 15508kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: -10
Time Limit Exceeded

input:

120000 993 998 991 196 712 911

output:


result: