链接：https://ac.nowcoder.com/acm/contest/330/H
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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


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

输入描述:

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

输出描述:

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

即如果概率等于a/b，a,b∈N 且 gcd(a,b)=1，你需要输出一个自然数 c<10^9+7 满足 bc≡a(mod10^9+7)

示例1

输入

复制

1 1 99

输出

复制

1

示例2

输入

复制

2 1 38

输出

复制

770000006

示例3

输入

复制

6 2 49

输出

复制

687500005

备注:

1≤n≤10^9
1≤k≤min{n,10^5}
0≤x≤99

题意：不说了~~

题解：求获奖概率，就用所有获奖的情况，除以总的情况。明白这个就好写了，然后再结合费马小定理求逆元，因为除法不能直接取模，需要取逆元，公式就是 A/B%mod=A%mod*B(的逆元)%MOD这样就可以了，然后B的逆元，就是B的(mod-2)次方，当然这是费马小定理求逆元，需要mod是质数。

再就是写公式了：公式就是每次选出i个人(i<=k-1) 选<=x的数(注意：有x+1个数)，剩下的n-1-i个人选>x的数(注意：有99-x个数)，最后求出所有情况，求和除以总的情况，就是： 这就是最后的公式~~，然后在实现上有点小技巧，看代码：

 

#include <iostream>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll n,k,x;
ll quick(ll a,ll b,ll c){//快速幂
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%c;
        b>>=1;
        a=(a*a)%c;
    }
    return ans%c;
}
int main(){
    cin >> n >> k >> x;
    ll w=quick(100,n-1,mod);//求100^n-1
    ll ***=quick(w,mod-2,mod);//求100^n-1的逆元
    ll ans=0;
    ll c=1;
    for (int i = 0; i <= k-1;i++){
        ll xx=quick(x+1,i,mod);//求(x+1)^i
        ll yy=quick(99-x,n-1-i,mod);//q求(99-x)^i
        ans=(ans+xx*yy%mod*c%mod)%mod;//求和，别忘了乘组合数c
        c=c*(n-i-1)%mod*quick(i+1,mod-2,mod)%mod;//求组合数的技巧，这里很重要，很妙，自己化简一下就知道
    }
    ans=ans****%mod;//最后乘以公式中分母的逆元，求出结果
    cout << ans << endl;
    return 0;
}
//除法都要换成乘以除数的逆元，求组合数用到，求最后结果用到！！！