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;

}

巴特西

codeforces div2_604 E. Beautiful Mirrors（期望+费马小定理）

最新文章

热门文章