[洛谷 5104]红包发红包

题目链接

https://www.luogu.org/problem/P5104

题解

因为我们在这里讨论的是每个人抢到红包的期望值，所以考虑红包提前就被抢光或者最后还有剩余这些内容都是没有意义的。（所以题目中给出的抢红包人数 \(n\) 对解题也没有帮助）

所以我们能做的就是找规律了：

• 对于第一个人而言，他期望情况下能抢到的钱范围在 \([0,w]\) 之间，那么他能抢到的钱的期望便是 \( \frac{w}{2} \)；
• 对于第二个人而言，他期望情况下能抢到的钱范围在 \([0,\frac{w}{2}]\) 之间，那么他能抢到的钱的期望便是 \( \frac{w}{4} \)；
• 以此类推，对于第 \(k\) 人而言，他期望情况下能抢到的钱范围在 \([0,\frac{w}{2^{k-1}}]\) 之间，那么他能抢到的钱的期望便是 \( \frac{w}{2^{k}} \)；

这里一直都在强调期望情况下这个概念。我们实际抢红包时抢到的钱的范围在绝大多数情况下都与期望值不同，但在这道题中，这些实际情况都不是我们应该考虑的。

#include <iostream>
#define MOD 1000000007
long long w,n,k,x,y;
using namespace std;
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1; 
 }
 return ans;
}
void ex_gcd(long long a,long long b,long long&x,long long&y)
{
 if(b==0)
 {
  x=1,y=0;
  return;
 }
 ex_gcd(b,a%b,x,y);
 int t=x;
 x=y;
 y=t-a/b*y;
 return;
}
int main()
{
 cin>>w>>n>>k;
 ex_gcd(fpow(2,k),MOD,x,y);
 cout<<w*(x+MOD)%MOD<<endl;
 return 0;
}