QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19828#1810. Generate the Sequencesconqueror_of_zky#AC ✓113ms3948kbC++141.5kb2022-02-11 17:36:242022-05-06 07:14:45

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-06 07:14:45]
  • 评测
  • 测评结果:AC
  • 用时:113ms
  • 内存:3948kb
  • [2022-02-11 17:36:24]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>

using namespace std;
const int mod=998244353; 
const int maxn=5e3; 
void add(int &x,int y){
	x+=y;
	if (x>=mod) x-=mod; 
}
int n,m,inv[maxn+5],fac[maxn+5],ivf[maxn+5],f[maxn+5][2]; 
int F[maxn+5]; 

int len; 
int C(int x,int y) {
	if (x<y) return 0;
	if (x<=maxn) return 1ll*fac[x]*ivf[x-y]%mod*ivf[y]%mod; 
	int ret=1; 
	for (int j=1;j<=y;j++) {
		ret=1ll*ret*(x-j+1)%mod;
		ret=1ll*ret*inv[j]%mod;
	}
	return ret; 
} 
void prework() {
	inv[1]=1; 
	for (int i=2;i<=maxn;i++) {
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; 
	}
	fac[0]=1; ivf[0]=1;
	for (int i=1;i<=maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for (int i=1;i<=maxn;i++) ivf[i]=1ll*ivf[i-1]*inv[i]%mod;
} 
int main() {
	prework();
	scanf("%d %d",&n,&m);
	n++;
	for (int i=3;i<=min(n,m);i++) {
		F[i]=C(m-2,i-2); 
	}
    f[n][0]=f[n][1]=1;
    for (int i=n-1;i>=1;i--) {
    		add(f[i][0],f[i+1][1]); 
    		add(f[i][1],f[i+1][0]); 
    		add(f[i][1],f[i+1][1]); 
    		add(f[i][0],f[i+1][0]); 
    	//	cout<<i<<' '<<j<<' '<<f[i][j]<<'\n'; 
    		for (int k=i+2;k<=n;k++) {
    			add(f[i][0],1ll*f[k][1]*F[k-i+1]%mod*C(n-i-1,n-k)%mod*fac[k-i-1]%mod); 
    			add(f[i][1],1ll*f[k][0]*F[k-i+1]%mod*C(n-i-1,n-k)%mod*fac[k-i-1]%mod); 
			}
	//	}
	//	cout<<f[i]<<'\n'; 
	}
	printf("%d\n",f[1][0]); 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

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

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

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

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

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

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

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

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

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

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

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

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

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

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

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

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

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

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

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

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

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

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

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

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

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

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

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

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 78ms
memory: 3888kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

score: 0
Accepted
time: 113ms
memory: 3904kb

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

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

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

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

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

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

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

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

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

score: 0
Accepted
time: 83ms
memory: 3868kb

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

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

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

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

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

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

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

score: 0
Accepted
time: 49ms
memory: 3776kb

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

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

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

score: 0
Accepted
time: 45ms
memory: 3864kb

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

score: 0
Accepted
time: 108ms
memory: 3948kb

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

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

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

score: 0
Accepted
time: 25ms
memory: 3772kb

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

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

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'