QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546436#1810. Generate the SequencessurguttiAC ✓63ms3844kbC++171.3kb2024-09-04 02:35:272024-09-04 02:35:27

Judging History

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

  • [2024-09-04 02:35:27]
  • 评测
  • 测评结果:AC
  • 用时:63ms
  • 内存:3844kb
  • [2024-09-04 02:35:27]
  • 提交

answer

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const int mod = 998244353;

int power(int a, int b) {
	int r = 1;
	for (; b; b >>= 1, (a *= a) %= mod)
		if (b & 1)
			(r *= a) %= mod;
	return r;
}

const int N = 3000 + 7;

int fac[N];
int inv[N];

int C(int n, int k) {
	if (0 <= k && k <= n) {
		return fac[n] * inv[k] % mod * inv[n - k] % mod;
	}
	return 0;
}

int n, m;
int pv[N][2];
int dp[N][2];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	fac[0] = 1;
	for (int i = 1; i < N; i++)
		fac[i] = fac[i - 1] * i % mod;
	
	inv[N - 1] = power(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1) % mod;
	
	cin >> n >> m;

	int ans = 1;

	pv[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i; j++)
			for (int k : {0, 1})
				dp[j][k] = 0;

		for (int j = 1; j <= i; j++) {
			for (int k : {0, 1}) {
				dp[j][k] += pv[j - 1][k ^ 1];
				if (j < i) {
					dp[j][k] += pv[j][k] * ((m - 2) * j % mod + mod - (i - 1 - j)) % mod;
				}
				dp[j][k] %= mod;
			}
		}

		for (int j = 0; j <= i; j++) {
			for (int k : {0, 1}) {
				ans += dp[j][k] * C(n, i) % mod;
				ans %= mod;
				pv[j][k] = dp[j][k];
			}
		}
	}

	cout << ans << '\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

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

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

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

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

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

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

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

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

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

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

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

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

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

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

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

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

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

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

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

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

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

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

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

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

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

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

score: 0
Accepted
time: 63ms
memory: 3728kb

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 62ms
memory: 3728kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

score: 0
Accepted
time: 62ms
memory: 3816kb

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

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

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

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

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

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

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

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

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

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

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

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

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

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

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

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

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

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

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

score: 0
Accepted
time: 52ms
memory: 3732kb

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

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

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

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

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

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

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

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

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

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

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'