提交时间:2024-09-15 15:35:09

运行 ID: 32604

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1009, M = 309, Mod = 998244353; int fpow(int a, int b = Mod - 2) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % Mod; a = 1ll * a * a % Mod, b >>= 1; } return res; } int n, m, pw[N], ip[N], dp[2][N][M], pl[N][M], fl, ans; int C(int n, int m) { if (n < 0 || m < 0 || n < m) return 0; return 1ll * pw[n] * ip[m] % Mod * ip[n - m] % Mod; } signed main() { scanf("%d%d", &m, &n); pw[0] = ip[0] = 1; for (int i = 1; i <= 1000; i++) { pw[i] = 1ll * pw[i - 1] * i % Mod; ip[i] = fpow(pw[i]); } for (int i = 0; i <= 1000; i++) { pl[i][0] = 1; for (int j = 1; j <= m; j++) pl[i][j] = 1ll * pl[i][j - 1] * ip[i] % Mod; } dp[0][0][m] = 1; for (int i = 0; i < n; i++) { memset(dp[fl ^ 1], 0, sizeof(dp[fl ^ 1])); for (int j = 0; j < n; j++) { for (int k = 1; k <= m && i * k <= j; k++) { for (int x = 1; x <= k && j + x <= n; x++) { (dp[fl ^ 1][j + x][x] += 1ll * dp[fl][j][k] * C(k, x) % Mod * pl[i][k - x] % Mod) %= Mod; } } } fl ^= 1; int s = 0; for (int j = 1; j <= m; j++) s = (s + 1ll * dp[fl][n][j] * pl[i + 1][j]) % Mod; ans = (ans + 1ll * (i + 1) * s) % Mod; } printf("%lld\n", 1ll * ans * pw[n] % Mod); return 0; }