【题目来源】https://www.luogu.com.cn/problem/P5104【题目描述】红包redbag发明了一个抢红包的系统。这个抢红包系统是这样的假如现在有 w 元那么你抢红包能抢到的钱就是 [0,w]等概率均匀随机出的一个实数x。现在红包发了一个 w 元的红包有 n 个人来抢。那么请问第 k 个人期望抢到多少钱输出答案对 10^97 取模后的结果。【输入格式】一行三个整数wnk。【输出格式】第 k 个人期望抢到的钱数对 10^97 取模后的结果。【输入样例】2 1 1​​​​​​​【输出样例】1【数据范围】注意红包发明的抢红包系统和微信的抢红包系统不一样红包发明的抢红包系统中的钱不一定是整数分。对于 30% 的数据k1。另有 30% 的数据期望值取模前为整数k≤10。对于全部数据0w(10^97)n≤10^18k≤n。【算法分析】● 快速幂https://blog.csdn.net/hnjzsyjyj/article/details/143168167● 费马小定理若 p 为质数且整数 a 满足 gcd(a,p)1则 a^(p-1)≡1(mod p)。费马小定理表明在模质数 p 下a 的 p-1 次幂同余于 1。● 费马小定理与模逆元的联系1逆元定义若 ax≡1(mod p)则 x 称为 a 的模 p 逆元记作 a^(-1)。2逆元求解由费马小定理 a^(p-1)≡1(mod p) 知 a×a^(p-2)≡1(mod p)据此可推导出 a 的逆元 a^(-1)≡a^(p-2)(mod p)。3模数约束模数 p 必须为质数。​​​​​​​● 在区间 0 到 x 之间随机且均匀地取一个数其长期平均值必然是区间的中点也就是 x/2。因此第 k 个人期望领到的红包金额为 w/(2^k)这一等式在模运算下等价于 w 乘以 2^k 的逆元。根据费马小定理2^k 的逆元等于 2^k 的 MOD−2 次方该值可以通过快速幂高效求解。【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int MOD1e97; int fastPow(LL a,LL b) { LL ans1; while(b) { if(b 1) ansans*a%MOD; aa*a%MOD; b1; } return ans%MOD; } int main() { LL w,n,k; cinwnk; coutw*fastPow(fastPow(2,k),MOD-2)%MOD; } /* in:2 1 1 out:1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/143135845https://blog.csdn.net/hnjzsyjyj/article/details/159687664https://blog.csdn.net/hnjzsyjyj/article/details/146287418