QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32227#1810. Generate the SequencesAppleblue17AC ✓38ms3796kbC++843b2022-05-18 08:37:032022-05-18 08:37:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 08:37:04]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:3796kb
  • [2022-05-18 08:37:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=3300,mod=998244353;
 
int ksm(int f,int x){
	int tot=1;
	while(x){
		if(x & 1ll) tot=1ll*tot*f%mod;
		f=1ll*f*f%mod;
		x>>=1ll;
	}
	return tot;
}

int mul[N],inv[N];
void init(int lim){
	mul[0]=inv[0]=1;
	for(int i=1;i<=lim;i++) mul[i]=1ll*mul[i-1]*i%mod;
	inv[lim]=ksm(mul[lim],mod-2);
	for(int i=lim-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int C(int m,int n){
	if(m<0 || n<0 || m<n) return 0;
	return 1ll*mul[m]*inv[n]%mod*inv[m-n]%mod;
}

int n,m;
long long c[N],dp[N];

int main(){
	init(N-5);
	cin>>n>>m;
	c[0]=1;
	for(int i=1;i<=n;i++) c[i]=c[i-1]*(m-i-1)%mod;
	
	dp[n]=1;
	for(int i=n;i>=1;i--){
		dp[i-1]=(dp[i-1]+dp[i])%mod;
		for(int j=0;j<i;j++){
			dp[i-j-1]=(dp[i-j-1]+dp[i]*C(i-1,j)%mod*c[j]%mod)%mod;
		}
	}
	cout<<dp[0];
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

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

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

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

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

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

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

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

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

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

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

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

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

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

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

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

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

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

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

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

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

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

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

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

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

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

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

score: 0
Accepted
time: 34ms
memory: 3668kb

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 38ms
memory: 3616kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

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

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

score: 0
Accepted
time: 27ms
memory: 3740kb

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

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

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

score: 0
Accepted
time: 5ms
memory: 3612kb

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

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

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

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

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

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

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

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

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

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

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

score: 0
Accepted
time: 17ms
memory: 3740kb

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

score: 0
Accepted
time: 32ms
memory: 3668kb

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

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

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

score: 0
Accepted
time: 36ms
memory: 3752kb

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

score: 0
Accepted
time: 14ms
memory: 3724kb

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

score: 0
Accepted
time: 5ms
memory: 3768kb

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

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

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'