自动搬运

查看原文

来自洛谷，原作者为

	Itst 没钩选手瑟瑟发抖

搬运于2025-08-24 22:04:24，当前版本为作者最后更新于2018-09-30 22:58:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update On 2020.07.07: 优化阅读体验

题意简述：有 $N$ 个选项，最开始随机蒙，会进行 $N-2$ 次删除操作，必须在其中 $K$ 次删除操作后更换自己选择的答案，求最优策略下选到正确答案的概率。

前置知识：概率、有理数取余(不会戳这里)

不妨先考虑直接确定是否选中正解的最后一次更换。设最后一次更换时包括当前选择的选项共有 $x$ 个选项,前 $K-1$ 次更换获得错解的概率为 $P$，那么更换后选到正确答案的概率就是 $\frac{P}{x - 1}$。当 $P$ 确定时，$x$ 越小，概率越高。也就是说最后一次更换安排在最后一次删除后，就有 $P$ 的概率选到正解，这个概率显然是最高的。

那么需要考虑 $P$ 如何取得最大值。类似地，设第 $i(i \geq 2)$ 次更换时剩下 $x$ 个选项,前 $i-1$ 次更换获得错解的概率为 $P'$，那么当前选到错误答案的概率是 $P' \frac{x-2}{x-1} + (1-P')=1-\frac{P'}{x-1}$。当 $P'$ 确定时，$x$ 越大，获得错解的概率越高。

那么可以得到最优策略：在前 $K-1$ 次删出错解后更换，第 $K$ 次更换放在最后一次删除错解之后。利用上面的式子可以将概率算出来。

小心 0 的特判。

#include<bits/stdc++.h>
#define MOD 100000007
using namespace std;
inline int poww(long long a , int b){
    long long times = 1;
    while(b){
        if(b & 1)	times = times * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return times;
}
int main(){
    int n , k;
    scanf("%d%d" , &n , &k);
    if(k == 0)
        cout << poww(n , MOD - 2);
    else{
        k--;
        long long fz = n - 1 , fm = n;
        n -= 2;
        while(k){
            fz = ((fm = fm * n % MOD) - fz) % MOD;
            k--;
            n--;
        }
        cout << fz * poww(fm , MOD - 2) % MOD;
    }
    return 0;
}