10.27算法学习打卡

约 245 个字 26 行代码预计阅读时间 1 分钟

牛客10.27每日一题抢红包
描述
有一个软件的抢红包系统是这样设计的：假如现在红包里面还有 w 元，那么你抢红包能抢到的钱就是 [0,w][0,w] 等概率均匀随机出的一个实数 x。

现在有个人发了一个 w 元的红包，有 n 个人来抢。那么请问第 k 个人期望抢到多少钱？

输出答案对 10^9+7 取模后的结果。输入描述：输入一行空格隔开的三个整数，w(0≦w≦109),n,k(0≦k≦n≦10^{18)w(0≦w≦10}9),n,k(0≦k≦n≦10^18)，分别表示红包的总金额，抢红包的人数以及询问的是第几个人。输出描述：输出一行一个整数，表示第 k 个人期望抢到的钱数对 10^9+7 取模后的结果。

依旧大整数，依旧用到了快速幂算法运用费马小定理算取2的乘法逆元

C++
#include <iostream>
#define ll long long
const ll mod = 1000000007;
ll fast_pow(ll a, ll b, ll p) {
    a %= p;
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;

    }
    return ans;
}
using namespace std;

int main() {
    ll w, n, k;
    cin >> w >> n >> k;
    ll inv2 = fast_pow(2,mod-2,mod);
    ll inv2k = fast_pow(inv2,k,mod);
    ll ans = w*inv2k%mod;
    cout<<ans;
    return 0;
}  

10.27算法学习打卡

评论