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

dp[n]=0dp[n]=0dp[n]=0，所以
dp[n−1]=pndp[0]+1dp[n-1]=p_{n}dp[0]+1dp[n−1]=pn​dp[0]+1

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

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=pi;edge[i].second=1−piedge[i].first=p_{i};edge[i].second=1-p_{i}edge[i].first=pi​;edge[i].second=1−pi​

代码：

#include
#include
#include
using namespace std;
typedef long long ll;
vector> 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);
}