Applese 的大奖（C++）

题目描述

Applese 和它的小伙伴参加了一个促销的抽奖活动，活动的规则如下：有一个随机数生成器，能等概率生成 0∼99 之间的整数，每个参与活动的人都要通过它获取一个随机数。最后得到数字最小的 k 个人可以获得大奖。如果有相同的数，那么后选随机数的人中奖。

Applese 自然是最心急的一个，它会抢在第一个去按随机数。请你帮忙计算一下它能够中奖的概率。

输入描述:

仅一行三个正整数 n, k, x，分别表示参与抽奖的总人数（包括Applese）,中奖的人数和 Applese 获得的随机数。

输出描述:

输出一个正整数表示 Applese 中奖的概率 mod109+7mod10^9+7mod109+7。

即如果概率等于ab\frac{a} {b}ba​, a,b∈N 且 gcd(a,b)=1，你需要输出一个自然数 c&lt;109+7c&lt;10^9+7c<109+7 满足 bc≡a(mod109+7)bc≡a(mod10^9+7)bc≡a(mod109+7)

示例1

输入

1 1 99

输出

1

示例2

输入

2 1 38

输出

770000006

示例3

输入

6 2 49

输出

687500005

备注:

1≤n≤1091≤n≤10^91≤n≤109

1≤k≤minn,1051≤k≤min{n,10^5}1≤k≤minn,105

$0\le x\le 99$

解题思路：

枚举 Applese 的名次，分别计算概率。答案为：

∑i=0k−1Cin−1pi(1−p)n−i−1∑_{i=0}^{k−1} C_i^{n-1}p^i(1−p)^{n−i−1}∑i=0k−1​Cin−1​pi(1−p)n−i−1

其中?为随机到的数不大于 Applese 的概率。

预处理逆元递推组合数。

所以这整个代码就是在实现上面这个数学公式的过程。

解题代码：

#include 
    
     #define LL long longusing namespace std;const LL mod=1e9+7;LL ksm(LL a,LL b)//快速幂{
        LL ans = 1;    a %= mod;    while( b>0 )    {
            if( b&1 ) ans = (ans*a)%mod;        b >>= 1;//位运算，右移1位，相当于除以2        a = (a*a)%mod;    }    return ans;}int main(){
        ios::sync_with_stdio(0);    LL n,k,x;//抽奖的总人数(包括Applese),中奖的人数和Applese获得的随机数    cin >> n >> k >> x;    LL p1 = (x+1)*ksm(100,mod-2)%mod;    LL p2 = (99-x)*ksm(100,mod-2)%mod;//p2=1-p1    LL ans=0,c=1;    for(int i=0;i