luogu P6835 概率DP 期望

时间:2024-09-20 15:36:20

luogu P6835 概率DP 期望

洛谷 P6835

原题链接

题意

n + 1个节点,第i个节点都有指向i + 1的一条单向路,现在给他们添加m条边,每条边都从一个节点指向小于等于自己的一个节点,现在从1号点开始走,每次等概率地选择出边,问到达n+1的步数期望

思路
  • 用 \(F_{i,j}\) 代表从i到j的期望步数

  • 由于期望的线性性质,所以 \(F_{i,k} + F_{k,j} = F_{i,j}\) 所以我们算出每个 \(F_{i,i+1}\) 即可

  • 对于当前节点i,出度为 \(d_i\), 所以选某条边的概率为

\[\frac{1}{d_i}
\]
  • 选直接连接i+1的那条边,步数为1,即期望步数为1 / d,而选择其他边的期望步数为
\[\frac{\sum_{j\in v[i]}{(1 + F_{j,i} + F_{i,i+1})}}{d_i}
\]
  • 上面式子像是一个“递归式”左右都有我们希望计算的\(F_{i,i+1}\),整理如下:
\[F_{i,i+1} = \frac{1}{d_i} + \frac{\sum_{j\in v[i]}{(1 + F_{j,i} + F_{i,i+1})}}{d_i}
\]

\[d_i * F_{i,i+1} = 1 + \sum_{j\in v[i]}{(1 + F_{j,i} + F_{i,i+1})}
\]

\[d_i * F_{i,i+1} = 1 + d_i - 1 + (d_i - 1) * F_{i,i+1} + \sum_{j\in v[i]}{F_{j,i}}
\]

\[F_{i,i+1} = d_i + \sum_{j\in v[i]}{F_{j,i}}
\]

其中 \(F_{j,i}\) 可以前缀和得到,最终复杂度为线性

注意:

  • 前缀和取模处理难免有后面的值小于前面的时候,所以每次相减时要加一个mod防止变为负数
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std; const long long modd = 998244353; int n, m;
long long ff[1000005] = {0};
vector<int> vv[1000005];
long long su[1000005] = {0}; int main()
{
int id;
scanf("%d%d%d", &id, &n, &m);
for (int i = 1; i <= m; ++i)
{
int xx, yy;
scanf("%d%d", &xx, &yy);
vv[xx].push_back(yy);
}
for (int i = 1; i <= n; ++i)
{
long long d = vv[i].size();
ff[i] = d + 1;
for (unsigned int j = 0; j < d; ++j)
{
ff[i] = (ff[i] % modd + (su[i - 1] - su[vv[i][j] - 1] + modd) % modd) % modd;
}
su[i] = (su[i - 1] % modd + ff[i] % modd) % modd;
}
printf("%lld\n", su[n]);
return 0;
}