noi.ac 277 游戏

见注释。

另递推求逆元特别慢，效率要求高的地方不要用。

// #include <iostream>
#pragma GCC optimize("O3")
#include <cstdio>
#include <utility>
using int_t = long long int;
// using std::cin;
// using std::cout;
// using std::endl;

const int mod = 1e9 + 7;
const int_t LARGE = 2e7;
int_t power(int_t base, int_t index) {
    index = (index % (mod - 1) + mod - 1) % (mod - 1);
    int_t result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}

int fact[LARGE + 1], inv[LARGE + 1], factInv[LARGE + 1], inv2[LARGE + 1];
inline int C(int n, int m) {
    // if (n < m) return 0;
    return (int_t)fact[n] * factInv[m] % mod * factInv[n - m] % mod;
}
//把2n个带标号元素划分成n个大小为2的集合的方案数（集合内无序）
inline int G(int n) {
    return (int_t)fact[2 * n] * inv2[n] % mod * factInv[n] % mod;
}
//至少淘汰了m个玩家的方案数
inline int F(int n, int m) {
    // if (n < m) return 0;
    if (m == 0) return G(n);
    //前半部分把2n-m个元素划分成m段，每段再塞一个被淘汰的玩家，后半部分钦定剩下的随便选。
    // 2n个元素本身未考虑循环同构。
    return (int_t)2 * n * inv[m] % mod * C(2 * n - m - 1, m - 1) % mod *
           G(n - m) % mod;
}
int main() {
    fact[0] = inv[1] = factInv[0] = fact[1] = factInv[1] = 1;
    inv2[0] = 1;
    int n, k;
    // cin >> n >> k;
    scanf("%d%d", &n, &k);
    inv2[1] = (mod - mod / 2);
    for (int i = 2; i <= 2 * n; i++) {
        // inv[i] = (int_t)(mod - mod / i) * inv[mod % i] % mod;
        fact[i] = (int_t)fact[i - 1] * i % mod;
        inv2[i] = (int_t)inv2[i - 1] * inv2[1] % mod;
    }
    // factInv[i] = (int_t)factInv[i - 1] * inv[i] % mod;
    factInv[2 * n] = power(fact[2 * n], -1);
    for (int_t i = 2 * n; i >= 1; i--) {
        inv[i] = (int_t)factInv[i] * fact[i - 1] % mod;
        factInv[i - 1] = (int_t)factInv[i] * i % mod;
    }
    int result = 0;

    for (int i = k; i <= n; i++) {
        result = (result + (int_t)(((i - k) & 1) ? (mod - 1) : 1) * C(i, k) %
                               mod * F(n, i) % mod) %
                 mod;
    }
    printf("%lld\n", (int_t)result * power(G(n), -1) % mod);
    return 0;
}