提交时间:2024-02-27 21:25:26

运行 ID: 26969

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int M = 321, Mod = 998244353; int fpow(int a, int b) { 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, K, f[2][M][M], g[2][M][M], fl, pw[M]; void Add(int &x, int y) {x = (x + y >= Mod ? x + y - Mod : x + y);} signed main() { scanf("%d%d%d", &n, &m, &K); if (n >= m) { printf("0\n"); return 0; } for (int i = 0; i <= n; i++) pw[i] = fpow(i, K); f[0][0][0] = 1; for (int i = 0; i < m; i++) { fl ^= 1; for (int j = 0; j <= n; j++) { for (int k = 0; k <= n; k++) f[fl][j][k] = g[fl][j][k] = 0; } for (int j = 0; j <= n; j++) { for (int k = 0; k <= j; k++) { Add(f[fl][j][k], f[fl ^ 1][j][k]); Add(f[fl][j + 1][k], f[fl ^ 1][j][k]); Add(f[fl][j][k + 1], f[fl ^ 1][j][k]); Add(f[fl][j + 1][k + 1], f[fl ^ 1][j][k]); Add(g[fl][j][k], g[fl ^ 1][j][k]); Add(g[fl][j + 1][k], g[fl ^ 1][j][k]); Add(g[fl][j][k + 1], g[fl ^ 1][j][k]); Add(g[fl][j + 1][k + 1], g[fl ^ 1][j][k]); } } for (int j = 0; j <= n; j++) { for (int k = 0; k <= j; k++) { g[fl][j][k] = (g[fl][j][k] + 1ll * pw[j - k] * f[fl][j][k]) % Mod; } } } printf("%d\n", g[fl][n][n]); return 0; }