投硬币

NC24641. 投硬币

描述

$\mathfrak{never} \,\, \mathfrak{thought} \,\, \mathfrak{I} \,\, \mathfrak{could} \,\, \mathfrak{become} \,\, \mathfrak{this} \,\, \mathfrak{strong} \,\, \mathfrak{in} \,\, \mathfrak{my} \,\, \mathfrak{whole} \,\, \mathfrak{life}$
你在练习 dp，你每一次会有 p 的概率成功，1-p 的概率失败
求投 n 次后，至少有 k 次成功的概率

答案模 998244353，其中 $0 \le k,n \le 10^5,0 \le p < 998244353$

实际上给你的这个概率是在模 998244353 意义下的，换句说 $p \equiv \frac{a}{b} \pmod {998244353}$

输入描述

第一行三个整数 n,k,p

输出描述

一行一个整数表示答案对 998244353 取模的结果

示例1

输入:

34 21 56

输出:

345738771

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 36ms, 内存消耗: 1288K, 提交时间: 2019-05-24 23:00:54

#include <cstdio>
#include <iostream>
#define ll long long 
using namespace std;
const ll maxn=1e5+5;
const ll m=998244353;
ll n,k,p,ans,c[maxn];
ll mpow(ll Base,ll Times){
	ll res=1;
	for (;Times;Times>>=1){
		if (Times&1){
			res=res*Base%m;
		}
		Base=Base*Base%m;
	}
	return res;
}
int main(){
	cin>>n>>k>>p;
	c[0]=1;
	for (int i=1;i<=n;i++){
		c[i]=(c[i-1]*(n-i+1)%m)*mpow(i,m-2)%m;
	}
	for (int i=k;i<=n;i++){
		ans+=((c[i]*mpow(p,i))%m*mpow(1-p+m,n-i))%m;
	}
	printf("%lld\n",ans%m);
	return 0;
}