codeforces div2_604 E. Beautiful Mirrors(期望+费马小定理)

题目链接:https://codeforces.com/contest/1265/problem/E

题意:有n面镜子,你现从第一面镜子开始询问,每次问镜子“今天我是否美丽”,每天可以询问一次,第 i 面镜子回答“美丽”的可能性是Pi/100,如果第i面镜子回答的是美丽,那么第下一天继续询问第i + 1面镜子。如果第i面镜子回答的是“不美丽”,那么下一天你将重新从第1面镜子询问。如此过程直到所有的镜子都回答“美丽”才算结束,求所有镜子都回答“美丽”所花费天数的期望值。

思路:首先第i面镜子回答“美丽”的概率是Pi/100,那么通过这一天所花费的期望就是100/Pi,假设到前i-1天所花费的期望天数是t,那么前i天所花费的期望就是(t+1)*(100/Pi),t+1是因为从第i-1天到第i天需要一天,再乘以100/Pi是期望值的计算。

       那么因为题意是要求天数在mod = M的剩余集下,所以我们所求的100/Pi设为x,则 x = (100/Pi)%M,x = 100*pi^(-1)%M,移项得,x*Pi ≡ 100%M,

我们把100提出来,求一下x1 * Pi ≡ 1 %M,最后求得的x1再乘100%M就是x了,即x = x1*100%M,求解x1的过程用费马小定理即可。因为M是素数,且M和Pi必定互素,所以有Pi*Pi^(M-2)≡1%M(费马小定理),x1 = Pi^(M-2),这里用快速幂即可计算出x1.

AC代码:

#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod =  998244353; 
ll quick_pow(ll a,ll x){
    ll res = 1;
    while(x){
    	if(x&1) res = res*a%mod;
		a = a*a%mod;
		x>>=1;
	}
	return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;cin>>n;
    ll res = 0;
    for(int i = 0;i<n;i++){
    	ll t;
		cin>>t;
		t = 100*quick_pow(t,mod-2)%mod;//计算x1 = Pi^(M-2) ,x1*100%M = x 
    	res = (res+1)*t%mod;
	}
	cout<<res;
    return 0;
}
原文地址:https://www.cnblogs.com/AaronChang/p/12129614.html