Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32666 | Aquizahv | 【S】T2 | C++ | 通过 | 100 | 668 MS | 11708 KB | 1876 | 2024-09-22 11:09:11 |
#include <bits/stdc++.h> using namespace std; const int N = 305, K = 1005, MOD = 998244353; int n, k, fac[K], inv[K], pows[K][K], invpows[K][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); for (int i = 1; i <= lmt; i++) { pows[i][0] = invpows[i][0] = 1; for (int j = 1; j <= lmt; j++) pows[i][j] = mmul(pows[i][j - 1], i); invpows[i][lmt] = mdiv(1, pows[i][lmt]); for (int j = lmt - 1; j >= 1; j--) invpows[i][j] = mmul(invpows[i][j + 1], i); } } 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 = 0; i <= k; i++, I ^= 1) { memset(f[I ^ 1], 0, sizeof(f[I ^ 1])); for (int j = 0; j <= k; j++) for (int p = 1; p <= n; p++) if (f[I][j][p]) for (int q = 1; q <= p && q + j <= k; q++) f[I ^ 1][j + q][q] = madd(f[I ^ 1][j + q][q], mmul(f[I][j][p], mmul(C(p, q), invpows[i][q]))); for (int p = 1; p <= n; p++) ans = madd(ans, mmul(f[I ^ 1][k][p], i));//, printf("%d%c", f[i][k][p], " \n"[p == n]); } cout << mmul(fac[k], ans) << endl; return 0; }