题解 P4830 【Tomoya loves Nagisa 】

Itst · 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;
}