UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204070#170. 数数tkswls10058ms5228kbC++1.0kb2024-04-07 08:00:522024-04-07 12:03:19

answer

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(2)
using namespace std;
int n, f[55][55][2505], m;
const int mod = 998244353;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	if (m > n * n) {
		cout << 0;
		return 0;
	}
	f[n + 1][0][0] = 1;
	int op = 0, opp;
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= n * n; j++) {
			for (int k = 0; k <= n; k++) {
				if (!f[i + 1][k][j]) continue;
				op =  (n - i), opp = n - 2 * (n - i) + k;
				f[i][k + 1][j + i] = (	f[i][k + 1][j + i] + f[i + 1][k][j] * opp % mod) % mod;
				f[i][k + 1][j + i] = (	f[i][k + 1][j + i] + f[i + 1][k][j] * (op - k) % mod * opp % mod * 2 % mod) % mod;
				if (opp >= 2) f[i][k][j + 2 * i] = (f[i][k][j + 2 * i]  + f[i + 1][k][j] * opp % mod * (opp - 1) % mod) % mod;
				if (op - k >= 1) f[i][k + 2][j] = (f[i][k + 2][j ]  + f[i + 1][k][j] * (op - k) % mod * (op - k) % mod) % mod;
			}
		}
	}
	int ans = 0;
	for (int i = m; i <= n * n; i++) {
		ans = (ans + f[1][n][i]) % mod;
	}
	cout << ans;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

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

input:

6 25

output:

468000

result:

ok single line: '468000'

Test #2:

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

input:

9 55

output:

94864779

result:

ok single line: '94864779'

Test #3:

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

input:

10 70

output:

451961658

result:

ok single line: '451961658'

Test #4:

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

input:

19 188

output:

199080822

result:

ok single line: '199080822'

Test #5:

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

input:

20 233

output:

354115829

result:

ok single line: '354115829'

Test #6:

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

input:

18 200

output:

360483048

result:

ok single line: '360483048'

Test #7:

score: 10
Accepted
time: 4ms
memory: 4516kb

input:

46 1200

output:

744054009

result:

ok single line: '744054009'

Test #8:

score: 10
Accepted
time: 13ms
memory: 4856kb

input:

48 1333

output:

506724228

result:

ok single line: '506724228'

Test #9:

score: 10
Accepted
time: 23ms
memory: 5228kb

input:

50 1275

output:

263941435

result:

ok single line: '263941435'

Test #10:

score: 10
Accepted
time: 18ms
memory: 5224kb

input:

50 1800

output:

763816424

result:

ok single line: '763816424'