CF1278F Cards 题解

namespace lowspeed_song {

int fac[N], inv[N], ifac[N], pwr[N], ipwr[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    pwr[0] = ipwr[0] = 1;
    for (int i = 1; i < N; ++i) {
        pwr[i] = pwr[i - 1] * 2 % mod;
        ipwr[i] = ipwr[i - 1] * i2 % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    int res = 1;
    for (int i = a; i > a - b; --i) res = res * i % mod;
    return res * ifac[b] % mod;
}

int S2[5010][5010];

inline void sol() {
    int n, m, k; cin >> n >> m >> k;
    S2[0][0] = 1;
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j <= i; ++j) S2[i][j] = (S2[i - 1][j] * j % mod + S2[i - 1][j - 1]) % mod;
    int res = 0;
    for (int i = 1; i <= k; ++i) res = (res + S2[k][i] * fac[i] % mod * binom(n, i) % mod * power(m, n - i, mod) % mod) % mod;
    cout << res * inversion(power(m, n, mod)) % mod << '\n';
}

} // namespace lowspeed_song