P14368 [JOISC 2018] 修行 / Asceticism 题解

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;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

inline void sol() {
    int n, k; cin >> n >> k;
    int res = 0;
    for (int i = 0; i <= k; ++i) {
        int val = binom(n + 1, i) * power(k - i, n, mod) % mod;
        if (i & 1) res = (res + mod - val) % mod;
        else res = (res + val) % mod;
    } cout << res << '\n';
}

} // namespace lowspeed_song