提交时间:2024-09-15 21:31:34

运行 ID: 32652

#include <bits/stdc++.h> using namespace std; const int N = 305, K = 1005, MOD = 998244353; int n, k, fac[K], inv[K]; int f[2][K][N], ans; int madd(int x, int y) { return (x + y) % MOD; } int msub(int x, int y) { return madd(x, MOD - y); } int mmul(int x, int y) { return 1ll * x * y % MOD; } int qpow(int x, int y) { int res = 1; while (y) { if (y & 1) res = mmul(res, x); x = mmul(x, x); y >>= 1; } return res; } int mdiv(int x, int y) { return mmul(x, qpow(y, MOD - 2)); } void init(int lmt) { fac[0] = inv[0] = 1; for (int i = 1; i <= lmt; i++) fac[i] = mmul(fac[i - 1], i); inv[lmt] = mdiv(1, fac[lmt]); for (int i = lmt - 1; i >= 1; i--) inv[i] = mmul(inv[i + 1], i + 1); } int C(int x, int y) { if (x < y) return 0; return mmul(fac[x], mmul(inv[x - y], inv[y])); } int main() { #ifdef aquazhao freopen("data.in", "r", stdin); // freopen("data.out", "w", stdout); #endif cin >> n >> k; init(max(n, k)); f[0][0][n] = 1; // for (int i = 1; i <= k; i++) // { // for (int j = 1; j <= k; j++) // for (int p = 1; p <= j && j + p <= k; p++) // { // for (int q = p; q <= n; q++) // { // // i = 2, j = 3, p = 1, q = 2 // f[i][j][p] = madd(f[i][j][p], mmul(f[i - 1][j - p][q], mdiv(C(q, p), qpow(i, p)))); // } // } // for (int p = 1; p <= n; p++) // ans = madd(ans, mmul(f[i][k][p], i)); // } for (int i = 1, I = 1; i <= k; i++, I ^= 1) { memset(f[I], 0, sizeof(f[I])); for (int j = 0; j < k; j++) for (int p = 1; p <= n; p++) if (f[I ^ 1][j][p]) for (int q = 1; q <= p && q + j <= k; q++) f[I][j + q][q] = madd(f[I][j + q][q], mmul(f[I ^ 1][j][p], mdiv(C(p, q), qpow(i, q)))); for (int p = 1; p <= n; p++) ans = madd(ans, mmul(f[I][k][p], i));//, printf("%d%c", f[i][k][p], " \n"[p == n]); } cout << mmul(fac[k], ans) << endl; return 0; }