Applese 的大奖(费马小定理求逆元)

Source
版权声明:本文章未经博主允许不得转载 https://blog.csdn.net/qq_42217376/article/details/86764029

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

  • 题目描述
    Applese 和它的小伙伴参加了一个促销的抽奖活动,活动的规则如下:有一个随机数生成器,能等概率生成 0∼99 之间的整数,每个参与活动的人都要通过它获取一个随机数。最后得到数字最小的 k 个人可以获得大奖。如果有相同的数,那么后选随机数的人中奖。
    Applese 自然是最心急的一个,它会抢在第一个去按随机数。请你帮忙计算一下它能够中奖的概率。
  • 输入描述:
    仅一行三个正整数 n, k, x,分别表示参与抽奖的总人数(包括Applese),中奖的人数和 Applese 获得的随机数。
  • 输出描述:
    输出一个正整数表示 Applese 中奖的概率 mod109+7。
    即如果概率等于a/b.a,b∈N 且 gcd(a,b)=1,你需要输出一个自然数 c<109+7 满足bc≡a(mod109+7)
  • 示例1
    输入
    1 1 99
    输出
    1
  • 示例2
    输入
    2 1 38
    输出
    770000006
  • 示例3
    输入
    6 2 49
    输出
    687500005
  • 备注:
    1≤n≤109
    1≤k≤min{n,105}
    0≤x≤99

  我们首先假设Applese已经中奖了,如果剩下的某个人一定会中奖,那么他获奖的概率为(x+1)/100,[0,x]中有x+1个数,有可能获奖的概率为(99-x)/100,现在我们的目的是要找到剩下k-1个获奖的人,那么我们可以得到Cin-1((x+1)/100)i((99-x)/100)n-1-i,i∈[0,k-1]我们需要从剩下n-1个人找到k-1个获奖的人,那么在x左边获奖的人可能是[0,k-1]中的任意人数,剩下的人都在x的右边.所以上述公式求和即是Applese获奖的概率.对于除法运算求逆元即可.

  • 费马小定理求逆元
      在模为素数p的情况下,有 ap-1≡1 (mod p),那么ap-2≡a-1 (mod p) ,所以a的逆元为ap-2.

本题需要注意取模时的精度问题

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#define pi 3.1415926
#define mod 1000000007
using namespace std;

//typedef pair<int,int> Node;
typedef long long  LL;
const int Max_n=100005;
int a[Max_n],f[Max_n];

LL Qpow(LL a,LL b){
	LL ans=1;
	LL res=a;
	while(b){
		if(b&1) ans=(ans*res)%mod;
		res=(res*res)%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	LL n,k,x;
	scanf("%lld%lld%lld",&n,&k,&x);
	LL ans=0,c=1;
	LL p=((x+1)*Qpow(100,mod-2))%mod;
	LL q=((99-x)*Qpow(100,mod-2))%mod;
	for(int i=0;i<k;i++){
		if(i)//求组合数
			c=((c*(n-i))%mod*Qpow(i,mod-2))%mod;//这里注意精度问题
		ans+=((c*Qpow(p,i))%mod*Qpow(q,n-i-1))%mod;//这里注意精度问题
		ans%=mod; 
	}
	printf("%lld\n",ans);
	return 0;
}