題目鏈接

http://codeforces.com/contest/1264/problem/C

題解

吐槽：為什么我賽后看cf的題就經常1h內做出Div.1 C, 一打cf就動不動AB題不會啊……zblzbl
首先顯然斷點把序列分成幾部分，總答案就等于所有部分的答案之和。考慮如何求一部分內的答案。首先有個非常經典的dp是\(f_i\)表示期望多少次從\(i\)走到\(i+1\), 但是按此方法并不能（至少我不會）導出一個方便維護修改的做法。
這時可以轉換思路，考慮另一種DP，設\(f_i\)表示\(i\)這個點期望經過多少次，則有\(f_i=\frac{1}{p_i}f_{i+1}, f_{n+1}=1\), 即\(f_i=\frac{1}{\prod^n_{j=i}p_j}\).
然后就很容易維護了，只需要求后綴積及其后綴和即可。每次二分前驅后繼，算一算貢獻差即可。
時間復雜度\(O(n\log n)\).

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;const int N = 2e5; const int P = 998244353; set<int> b; llong p[N+3]; llong s[N+3],ss[N+3]; bool f[N+3]; int n,q; llong ans;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong mulinv(llong x) {return quickpow(x,P-2);}int getprv(int x) {set<int>::iterator iter=b.lower_bound(x); iter--; return *iter;}void Flip(int x) {int l = getprv(x),r = *b.upper_bound(x);llong tmp = (ss[l]-ss[x]+P)%P,coe = f[x]==0?(s[x]-s[r]+P)%P:(s[r]-s[x]+P)%P;ans = (ans+tmp*coe)%P;if(!f[x]) {b.insert(x);} else {b.erase(x);}f[x]^=1; }int main() {scanf("%d%d",&n,&q);for(int i=1; i<=n; i++) {scanf("%lld",&p[i]); p[i] = p[i]*mulinv(100)%P;}b.insert(1); b.insert(n+1); f[1] = 1;s[n+1] = 1ll; for(int i=n; i>=1; i--) {s[i] = s[i+1]*p[i]%P; ss[i] = (mulinv(s[i])+ss[i+1])%P;}ans = ss[1];for(int i=1; i<=q; i++){int x; scanf("%d",&x);Flip(x);printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 1264C/1265E Beautiful Mirrors with queries (概率期望、DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。