每日一题：大逃离

题意

从 $n$ 个数中任选 $k$ 个数，取得这 $k$ 个数中最大的一个数，求每个数被取得的概率。$(n, k \in [1, 2e5])$

Solution

将数组排序后，枚举每个数被作为最大值的可能性，当第 $i$ 个数作为最大值时，其它 $k - 1$ 个一定从前 $i - 1$ 个里面选，即方案数为 $C(i - 1, k - 1)$，将其除以总方案数 $C(n, k)$ 即为被取得概率。

Code

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param k int整型 
     * @param Point int整型vector 
     * @return int整型vector
     */
    long long mod = 1e9 + 7;
    long long f[200005];
    long long qp(long long a, long long b) {
        long long sum = 1;
        while (b) {
            if (b & 1) sum = sum * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return (int)sum;
    }
    long long C(int n, int m){
        if(n == m || m == 0) return 1;
        return f[n] * qp(f[m], mod - 2) % mod * qp(f[n - m], mod - 2) % mod;
    }
    vector<int> city(int n, int k, vector<int>& a) {
        // write code here
        auto b = a;
        sort(a.begin(), a.end());
        vector<int> g;
        map<int, long long> mp;
        f[0] = 1;
        for (long long i = 1; i <= 200000; ++i) {
            f[i] = f[i - 1] * i % mod;
        }
        for (int i = 0; i < n; ++i) {
            if (i + 1 >= k) 
                mp[a[i]] = C(i, k - 1);
        }
        long long sum = C(n, k);
        for (int i = 0; i < n; i++) {
            g.push_back(mp[b[i]] * qp(sum, mod - 2) % mod);
        }
        return g;
    }
};