逆元 适用 mod 为素数 C(n, m) 函数适用 n, m 在 1kw 以下时 n 过大时可暴力 均过大用 lucas定理 小于等于 k 种颜色 k * (k - 1) ^ (n - 1) 减去 (k - 1) * (k - 2) ^ (n - 1) * (不选的 k 种可能颜色) 有重复减去的部分 选 i 种颜色的情况数为 C(k, i) #include <bits/stdc++.h> #define ll long long const long long mod = 1e9 + 7; using namespace std; ll Pow(ll a, ll b) // 快速幂 { ll ans = 1; ll t = a; while (b != 0) { if (b & 1) ans = (ans * t) % mod; t = (t * t) % mod; b >>= 1; } return ans; } /// C(n, m) 组合数函数 ll fac[1000005], inv[1000005], num[1000005]; void init(int p) { fac[0] = 1; for (int i = 1; i <= p; i++) fac[i] = fac[i - 1] * i % mod; inv[p] = Pow(fac[p], mod-2); for (int i = p - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod; } ll C(ll n, ll m) { return fac[n] * inv[m] % mod * inv[n - m] % mod; } int main() { init(1000004); /// int T; scanf("%d", &T); for (int cas = 1; cas <= T; cas++) { ll n, m, k; scanf("%lld %lld %lld", &n, &m, &k); ll ans = 0; ll t = 1; for (int i = k; i > 0; i--, t = (-1) * t) /// 容斥 ans = (ans + t * C(k, i) % mod * i % mod * Pow(i - 1, n - 1) % mod + mod) % mod; // ans *= C(m , k) m太大, 暴力加逆元 for (int i = m; i >= m - k + 1; i--) ans = ans * i % mod; ans = ans * inv[k] % mod; printf("Case #%d: %lld\n", cas, ans); } return 0; }
