codeforces# Round 604-E. Beautiful Mirrors(期望DP)
鏈接：
https://codeforces.com/contest/1265/problem/E
題意：
Examples
input
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n42" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">1
50</pre>
output
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n45" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">2</pre>
input
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n48" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">3
10 20 50</pre>
output
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n51" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">112</pre>
Note
In the first test, there is only one mirror and it tells, that Creatnx is beautiful with probability 1/2. So, the expected number of days until Creatnx becomes happy is 2.
有n個鏡子，每個鏡子有pi/100的概率回答是，初始從1開始，如果詢問鏡子回答為是，則下一天將詢問第i+1個鏡子，當(dāng)?shù)趎個鏡子回答是時，游戲結(jié)束。如果鏡子回答為否，則下一天將重新訪問第1個鏡子。求游戲結(jié)束的期望步數(shù)。
思路：經(jīng)典概率DP + 快速冪+費馬定理+逆元:
代碼：
<pre mdtype="fences" cid="n70" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">#include <bits/stdc++.h>
using namespace std;
define ll long long
const ll mod = 998244353;
const int maxn = 2e5+10;
ll dp[maxn];
ll pow(ll a, ll b){
ll res=1;
while(b){
if(b&1){
res = (resa) % mod;
}
a = (aa) % mod;
b >>= 1;
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
int n;
cin >> n;
for(int i=1; i<=n; i++){
ll x;
cin >> x;
ll p = 100 * pow(x, mod-2) % mod;
dp[i] = (dp[i-1]+1)*p%mod;
}
cout << dp[n] << endl;
return 0;
}</pre>
知識點：
-
同余定理：
給定一個正整數(shù)m，如果兩個整數(shù)a和b滿足a-b能夠被m整除，即(a-b)/m得到一個整數(shù)，那么就稱整數(shù)a與b對模m同余，記作a≡b(mod m)。對模m同余是整數(shù)的一個等價關(guān)系。例如26≡2(mod 12)。
-
費馬小定理：
[圖片上傳失敗...(image-25cb07-1576556846159)]
，其中 [圖片上傳失敗...(image-93433d-1576556846159)]
為任意質(zhì)數(shù)而 [圖片上傳失敗...(image-751c0-1576556846159)]
為與其互質(zhì)的任意整數(shù)。
-
逆元：
對于正整數(shù)逆元一般用擴展歐幾里得算法來求得，如果和img，如果有img，那么把這個同余方程中img的最小正整數(shù)解叫做img模img的逆元。img
有關(guān)求逆元的方法，我在學(xué)習(xí)之后會更新（^ ^)。
