抖音网站九易建网站的建站流程

题：爬树的甲壳虫
题意： 现在有一个甲壳虫，它可以从树的$i-1$高度爬到树的$i$高度。但是爬上去之后就会以$p_i$的概率从树上掉到0高度，则以$1-pi$的概率掉不下来。爬行一个高度花费一个时间1，问从0爬到高度$n$的期望时间是多少？
通过题意描述可以简单的写出$dp$方程，设$dp[i]$为从高度$i$爬到高度$n$所需要花费的时间。
$$dp[i-1]=p_{i}dp[0]+(1-p_i)dp[i]+1$$
其中$1$是必须要花费的时间，剩下的都是后续时间。
如果把$dp$设置成从0高度到达i的时间就列不出来，不知道咋写。
但是写出来这个方程需要进行进一步推导，容易得出来两个式子：
$$dp[n-1]=p_{n}dp[0]+(1-p_n)dp[n]+1$$
$$dp[0]=p_{1}dp[0]+(1-p_1)dp[1]+1$$

$dp[n]=0$，所以
$$dp[n-1]=p_{n}dp[0]+1$$

以此类推，就会发现，$dp[1]$可以表示成$k\times dp[0]+b$的形式.
接下来设新的$dp$为$f[i][0]$和$f[i][1]$，并且$f[i][0]$为$i$状态下的$k$，$f[i][1]$为$i$状态下的$b$。进行下面的状态转移：

for (int i = n - 2; i >= 0; i--){f[i][0] = ((ll)f[i + 1][0] * (edge[i+1].second)%mod + (ll)edge[i + 1].first)%mod;f[i][1] = (((ll)f[i + 1][1] * (edge[i + 1].second)%mod) + (ll)1)%mod;}

其中$edge[i].first=p_i;edge[i].second=1-p_i$

代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
vector<pair<int, int>> edge;
const int length = 1e5 + 5;
int mod = 998244353;
int dp[length][2];int rev1(int x)
{int t = mod - 2;int ans = 1;while (t){if (t % 2 == 1){ans = (ll)ans * x%mod;}x = (ll)x*x%mod;t = t >> 1;}return ans;
}
void opr()
{for (int i = 0; i < edge.size(); i++){int a = edge[i].first;int b = edge[i].second;int tmp = (ll)a * rev1(b)%mod;edge[i].first = tmp;//p_{i}edge[i].second = (1ll - tmp + mod) % mod;//1-p_{i}}
}
int main(void)
{int n;scanf_s("%d", &n);for (int i = 0; i < n; i++){int x1, y1;scanf_s("%d%d", &x1, &y1);edge.push_back({ x1,y1 });}opr();//把edge处理成mod p的pi和(1-pi)的形式edge.insert(edge.begin(),{ 0,0 });dp[n - 1][0] = edge[n].first;dp[n - 1][1] = 1;for (int i = n - 2; i >= 0; i--){dp[i][0] = ((ll)dp[i + 1][0] * (edge[i+1].second)%mod + (ll)edge[i + 1].first)%mod;dp[i][1] = (((ll)dp[i + 1][1] * (edge[i + 1].second)%mod) + (ll)1)%mod;}int ans = (ll)dp[0][1]*rev1(1 - dp[0][0] + mod)%mod;printf("%d",ans);
}