链接：https://ac.nowcoder.com/acm/contest/330/H
来源：牛客网
Applese 和它的小伙伴参加了一个促销的抽奖活动，活动的规则如下：有一个随机数生成器，能等概率生成 0∼99
之间的整数，每个参与活动的人都要通过它获取一个随机数。最后得到数字最小的 k 个人可以获得大奖。如果有相同的数，那么后选随机数的人中奖。
Applese 自然是最心急的一个，它会抢在第一个去按随机数。请你帮忙计算一下它能够中奖的概率。
仅一行三个正整数 n, k, x，分别表示参与抽奖的总人数（包括Applese）,中奖的人数和 Applese 获得的随机数。
输出一个正整数表示 Applese 中奖的概率 mod 1e9+7
首先是推出公式，在dalao的帮助下 理解了
枚举0 ～ k-1 ,因为 App 中奖了 然后就是 p1^i p2^(n-i-1)
其中 p1 为 小于等于 x 的概率
由于涉及除法取摸，需要求逆元。
逆元就是 A*B-1 == 1 (mod p) 把除法换成乘法
先学习了其中一个方法。 如果 a与p互质 可以用 费马小定理
ap-1 == 1 (mod p)
所以 上式可以写为 a*ap-2 == 1 (mod p)
那么 a的逆元就是 ap-2
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 6 ll powm(ll a,ll b=mod-2) { 7 ll sum=1,tmp=a%mod; 8 while(b) { 9 if(b&1) sum=sum*tmp%mod; 10 tmp=tmp*tmp%mod; 11 b>>=1; 12 } 13 return sum; 14 } 15 16 int main() { 17 int n,k,x; 18 ll val=powm(100); 19 scanf("%d%d%d",&n,&k,&x); 20 ll p1=(x+1)*val%mod; 21 ll p2=(99-x)*val%mod; 22 ll c=1,ans=0; 23 for(int i=0;i<k;i++) { 24 ans=ans+c*powm(p1,i)%mod*powm(p2,n-1-i)%mod; 25 ans=ans%mod; 26 c=c*(n-i-1)%mod*powm(i+1)%mod; 27 } 28 printf("%lld",ans); 29 }