QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#432060#1810. Generate the Sequencesgrass8cow#AC ✓29ms3988kbC++17845b2024-06-06 17:17:262024-06-06 17:17:28

Judging History

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

  • [2024-06-06 17:17:28]
  • 评测
  • 测评结果:AC
  • 用时:29ms
  • 内存:3988kb
  • [2024-06-06 17:17:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,f[3010],jx[3010];
const int mod=998244353,N=3e3;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
int jc[N+10],ij[N+10];
int C(int a,int b){
    if(a<b||a<0||b<0)return 0;
    return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int hv[N+10];
int main(){
    jc[0]=1;
    for(int i=1;i<=N;i++)jc[i]=1ll*i*jc[i-1]%mod;
    ij[N]=qpow(jc[N],mod-2);
    for(int i=N;i;i--)ij[i-1]=1ll*i*ij[i]%mod;
    scanf("%d%d",&n,&m);
    hv[0]=1;
    for(int i=1;i<=N;i++)hv[i]=1ll*hv[i-1]*(m-1-i)%mod;
    f[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1];
        for(int j=0;j<=i-1;j++)
            (f[i]+=1ll*C(i-1,j)*f[i-1-j]%mod*hv[j]%mod)%=mod;
    }
    printf("%d\n",f[n]);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3936kb

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

score: 0
Accepted
time: 4ms
memory: 3988kb

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

score: 0
Accepted
time: 29ms
memory: 3944kb

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 28ms
memory: 3892kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

score: 0
Accepted
time: 28ms
memory: 3860kb

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

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

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3876kb

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3920kb

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

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

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

score: 0
Accepted
time: 19ms
memory: 3856kb

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

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

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

score: 0
Accepted
time: 12ms
memory: 3932kb

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

score: 0
Accepted
time: 23ms
memory: 3944kb

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

score: 0
Accepted
time: 11ms
memory: 3880kb

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

score: 0
Accepted
time: 26ms
memory: 3884kb

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

score: 0
Accepted
time: 9ms
memory: 3844kb

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

score: 0
Accepted
time: 6ms
memory: 3928kb

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

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

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'