QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294192#4903. 细菌Bronya100 ✓950ms26832kbC++143.5kb2023-12-30 09:43:352023-12-30 09:43:35

Judging History

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

  • [2023-12-30 09:43:35]
  • 评测
  • 测评结果:100
  • 用时:950ms
  • 内存:26832kb
  • [2023-12-30 09:43:35]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
const int mo=998244353,G=3;
const int N=1000000;
int fact[N+5],ifact[N+5];
int fast_pow(int a,int p){
    int sum=1;
    while(p){
        if(p&1)sum=1ll*a*sum%mo;
        a=1ll*a*a%mo;
        p>>=1;
    }
    return sum;
}
const int invG=fast_pow(G,mo-2);
int rev[4000005];
int add(int u,int v){
    return (u+v>=mo?u+v-mo:u+v);
}
int C(int u,int v){
    if(u<v)return 0;
    return 1ll*fact[u]*ifact[v]%mo*1ll*ifact[u-v]%mo;
}
void Init(){
    fact[0]=1;
    for(int i=1;i<=N;i++)fact[i]=1ll*fact[i-1]*i%mo;
    ifact[N]=fast_pow(fact[N],mo-2);
    for(int i=N-1;i>=0;i--)ifact[i]=ifact[i+1]*1ll*(i+1)%mo;
}
void NTT(int *A,int len,bool op){
    for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)|(((i&1)?(len>>1):0));
    for(int i=0;i<len;i++)
        if(i<rev[i])swap(A[i],A[rev[i]]);
    for(int i=2;i<=len;i*=2){
        int now=i/2;
        int buf=fast_pow((op?G:invG),(mo-1)/i);
        for(int j=0;j<len;j+=i){
            int pg=1;
            for(int k=0;k<now;k++){
                int x=A[j+k],y=A[j+k+now];
                A[j+k]=add(x,1ll*y*pg%mo);
                A[j+k+now]=add(x,mo-1ll*y*pg%mo);
                pg=1ll*pg*buf%mo;
            }
        }
    }
    if(!op){
        int invL=fast_pow(len,mo-2);
        for(int i=0;i<len;i++)A[i]=1ll*A[i]*invL%mo;
    }
}
void times(int *A,int *B,int n){
    for(int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%mo;
}
void mul(int *A,int *B,int n,int lim){
    int L=1;while(L<=2*n)L<<=1;
    static int sav[4000005];
    memcpy(sav,B,sizeof(int)*L);
    NTT(A,L,1);NTT(B,L,1);
    times(A,B,L);
    NTT(A,L,0);
    memset(A+lim,0,sizeof(int)*(L-lim));memset(sav,0,sizeof(int)*L);
}
namespace Subtaskk1{
    int f[120005],g[120005];
    void Solve(int *A,int d,int n,int x){
        for(int i=0;i<=n+1;i++)f[i]=g[i]=0;
        f[x]=1;A[0]=1;
        for(int i=1;i<=d;i++){
            for(int j=1;j<=n;j++)g[j]=add(f[j-1],f[j+1]);
            for(int j=1;j<=n;j++){
                f[j]=g[j];g[j]=0;
                A[i]=add(A[i],f[j]);
            }
        }
    }
}
namespace Subtaskk2{
    int calc(int x,int y,int u,int v,int op){
        if(x<0||y<0)return 0;
        if(x==0&&y==0)return 1;
        int sav=C(x+y,x);
        swap(x,y);
        if(!op)x-=u,y+=u;
        else x-=v,y+=v;
        return add(sav,mo-calc(x,y,u,v,op^1));
    }
    int calc2(int x,int y,int u,int v){
        if(x==0&&y==0)return 1;
        if(x<0||y<0||y-x>=u||y-x<=v)return 0;
        return add(C(x+y,x),mo-add(calc(y-v,x+v,u,v,0),calc(y-u,x+u,u,v,1)));
    }
    void Solve(int *A,int d,int n,int x){
        int u=x,v=-(n-x+1);A[0]=1;
        for(int i=1;i<=d;i++){
            A[i]=add(A[i-1],A[i-1]);
            if((i-1-u)%2!=0)A[i]=add(A[i],mo-calc2((i-u)/2,i-1-(i-u)/2,u,v));
            if((i-1-v)%2!=0)A[i]=add(A[i],mo-calc2((i-v-2)/2,i-1-(i-v-2)/2,u,v));
        }
    }
}
int main(){
    static int X[4000005],Y[4000005],Z[4000005];
    int d,n,m,k,a,b,c;Init();
    scanf("%d%d%d%d%d%d%d",&d,&n,&m,&k,&a,&b,&c);
    if(1ll*n*n<=d)Subtaskk1::Solve(X,d,n,a);
    else Subtaskk2::Solve(X,d,n,a);
    if(1ll*m*m<=d)Subtaskk1::Solve(Y,d,m,b);
    else Subtaskk2::Solve(Y,d,m,b);
    if(1ll*k*k<=d)Subtaskk1::Solve(Z,d,k,c);
    else Subtaskk2::Solve(Z,d,k,c);
    for(int i=0;i<=d;i++){
        X[i]=1ll*X[i]*ifact[i]%mo;
        Y[i]=1ll*Y[i]*ifact[i]%mo;
        Z[i]=1ll*Z[i]*ifact[i]%mo;
    }
    mul(X,Y,d+1,d+1);mul(X,Z,d+1,d+1);
    printf("%d\n",1ll*X[d]*fact[d]%mo);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 11ms
memory: 20208kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

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

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: 14ms
memory: 20260kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 15ms
memory: 22384kb

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: 172ms
memory: 22824kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 187ms
memory: 25592kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 85ms
memory: 25396kb

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: 82ms
memory: 24364kb

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: 99ms
memory: 25432kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 95ms
memory: 22980kb

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: 258ms
memory: 23664kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 661ms
memory: 22276kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 528ms
memory: 24380kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 454ms
memory: 23544kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 390ms
memory: 24348kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 350ms
memory: 22888kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 287ms
memory: 26544kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 177ms
memory: 26684kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 126ms
memory: 22808kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 109ms
memory: 25432kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 88ms
memory: 23364kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 90ms
memory: 22868kb

input:

120000 119996 119994 1 58014 49559 1

output:

682979057

result:

ok 1 number(s): "682979057"

Subtask #7:

score: 10
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

Test #23:

score: 10
Accepted
time: 344ms
memory: 24856kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 950ms
memory: 25540kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 743ms
memory: 25520kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 630ms
memory: 26668kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 543ms
memory: 26680kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 480ms
memory: 24800kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 386ms
memory: 24764kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 224ms
memory: 24236kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 146ms
memory: 24312kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 115ms
memory: 26832kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 87ms
memory: 25520kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 91ms
memory: 25520kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"