傳送門

文章目錄

• 題意：
• 思路：

題意：

要從$1$走到$n$，每次成功走下去的概率為$\frac{p_i}{100}$，如果不成功那就回到$1$號(hào)點(diǎn)繼續(xù)走。問走完$n$個(gè)點(diǎn)的期望是多少。

思路：

以前見過這種失敗了就回到起點(diǎn)的期望$dp$，但還是想了很久。
考慮$f[i]$表示到當(dāng)前點(diǎn)的期望步數(shù)。如果成功了的話，那就是直接從$f[i?1]$轉(zhuǎn)移過來就行。如果失敗了的話，那就是從$i?1$走過來，但是回到了起點(diǎn)，再加上到$i$點(diǎn)的期望就行啦，寫成$dp$方程的形式是這樣的：$$f[i]=(f[i?1]+1)?\frac{p_i}{100}+(f[i?1]+f[i]+1)?\frac{100?p_i}{100}$$化簡一下就是$$f[i]=\frac{100?(1+f[i?1])}{p[i]}$$用快速冪求逆元就行啦。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=998244353,INF=0x3f3f3f3f; const double eps=1e-6;int n; LL p[N],f[N];LL qmi(LL a,LL b) {LL ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&p[i]);for(int i=1;i<=n;i++) f[i]=100*(1+f[i-1])%mod*qmi(p[i],mod-2)%mod;printf("%lld\n",f[n]%mod);return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #604 (Div. 2) E. Beautiful Mirrors 期望dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。