CF1716F

下降幂每次都重新计算会TLE :)

#include <cstdio>
#include <assert.h>

using namespace std;

using ll = long long;

const int mod = 998244353;
ll s[(int)2e3 + 9][(int)2e3 + 9] = {1};
ll n, m, k, tt;

ll cal(ll x, ll t)
{
    ll res = 1;
    for (ll i = x; i >= x - t + 1; --i)
        res = i * res % mod;
    return res;
}

ll powmod(ll a, ll b)
{
    ll res = 1;
    for (; b > 0; b >>= 1, a = a * a % mod)
        if (b & 1)
            res = res * a % mod;
    return res;
}

void solve()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    ll xjm = 1;
    ll ans = 0, x = (m + 1) / 2, y = m / 2;
    for (int i = 0; i <= k && n >= i; ++i)
        ans = (ans + s[k][i] * xjm % mod * powmod(x, i) % mod * powmod(m, n - i)) % mod, xjm = xjm * (n - i) % mod;
    printf("%lld\n", ans);
}

int main()
{
    for (int i = 1; i <= 2e3; ++i)
        for (ll j = 1; j <= 2e3; ++j)
            s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * j) % mod;
    scanf("%lld", &tt);
    for (int i = 1; i <= tt; ++i)
        solve();
}