CF1716F

发表于 更新于 分类于 本文字数： 190 阅读时长 ≈ 1 分钟

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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();
}