概率dp

f[x]表示能走到x号城市的概率, f[1] = 1

考虑从x号城市出发到y号城市的高速公路, 通过x号城市走到y号城市的概率有多大?

f[y] += f[x] / d[x], d[x]表示从x号城市出发的高速公路一共有多少条;

能走到y号城市的概率

pre(y)表示所有连接到y号城市的高速公路的起点的集合

时间复杂度\(O(n+m)\)

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
vector<int> c[110];
double f[110];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    c[x].push_back(y);
  }
  memset(f, 0, sizeof(f));
  f[1] = 1;
  for (int i = 1; i < n; i++) {
    int l = c[i].size();
    for (int j = 0; j < l; j++) f[c[i][j]] += f[i] / l;
  }
  printf("%10f\n", f[n]);

  return 0;
}

最简分数\(\frac{a}{b} \mod p\) 的意思时找到整数c使得\(bc \equiv a (mod \space p)\)

p是质数, 费马小定理, \(b^{p - 1} \equiv 1 (mod \space p)\)也就是说有\(b^{p - 2} \equiv b^{-1} (mod \space p)\),所有的\(\frac{a}{b}(mod \space p)\)可以用\(a* b^{p-2} (mod \space p)\)代替

\(b^{p-2}\mod{p}\)可以用快速幂

走到y号城市的概率\(f[y]=\sum_{x\in pre(y)}{f[x] * d[x]^{p-2}} \mod{p}\)

时间复杂度\(O(n+m\log{p})\)

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
vector<int> c[110];
LL f[110];
const int p = 1e9 + 7;
LL qmi(LL now, int k) {
  LL res = 1;
  for (; k; k >>= 1, now *= now, now %= p) {
    if (k & 1) res *= now, res %= p;
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    c[x].push_back(y);
  }
  memset(f, 0, sizeof(f));
  f[1] = 1;
  for (int i = 1; i < n; i++) {
    int l = c[i].size();
    for (int j = 0; j < l; j++) {
      f[c[i][j]] += f[i] * qmi(l, p - 2);
      f[c[i][j]] %= p;
    }
  }
  printf("%lld\n", f[n]);

  return 0;
}

期望定义:\(E(x)=\sum^{n}_{i}{x_{i}p_{i}}\)

分别算出经过1, 2, \(\dots\) , n -1条高速公路走到n号城市的概率

\(f[i][j]\)表示经过j条高速公路走到i号城市的概率,有:

答案:\(\sum^{n-1}_{i=1}{f[n][i]*i}\)

复杂度\(O(nm\log{p})\)

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
vector<int> c[110];
LL f[110][110];
const int p = 1e9 + 7;

LL qmi(LL now, int k) {
  LL res = 1;
  for (; k; k >>= 1, now *= now, now %= p) {
    if (k & 1) {
      res *= now;
      res %= p;
    }
  }
  return res;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    c[x].push_back(y);
  }
  memset(f, 0, sizeof(f));
  f[1][0] = 1;
  for (int i = 1; i < n; i++) {
    int l = c[i].size();
    for (int k = 0; k < n; k++) {
      if (f[i][k]) {
        for (int j = 0; j < l; j++) {
          f[c[i][j]][k + 1] += f[i][k] * qmi(l, p - 2);
          f[c[i][j]][k + 1] %= p;
        }
      }
    }
  }
  LL res = 0;
  for (int i = 1; i < n; i++) {
    res += f[n][i] * i;
    res %= p;
  }
  printf("%lld\n", res);

  return 0;
}

优化

用f[x]表示从x号城市出发经过多少条高速公路能到达n号城市, f[n] = 0;

由期望定义\(E(x)=\sum^{n}_{i}{x_ip_i}\)

有\(f[x] = \sum_{y\in nxt(x)}{\frac{f[y]+1}{d[x]}}=(\sum_{y\in nxt(x)}{\frac{f[y]}{d[x]}}) + 1\)

nxt(x)表示从x出发的高速公路终点的集合

时间复杂度\(O(m\log(p))\)

• 期望是从终点出发, 往起点转移
• 概率是从起点出发, 往终点转移

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
vector<int> c[110];
LL f[110];
const int p = 1e9 + 7;

LL qmi(LL now, int k) {
  LL res = 1;
  for (; k; k >>= 1, now *= now, now %= p) {
    if (k & 1) {
      res *= now;
      res %= p;
    }
  }
  return res;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    c[x].push_back(y);
  }
  memset(f, 0, sizeof(f));
  for (int i = n - 1; i; i--) {
    int l = c[i].size();
    f[i] = 1;
    for (int j = 0; j < l; j++) {
      f[i] += f[c[i][j]] * qmi(l, p - 2);
      f[i] %= p;
    }
  }
  printf("%lld\n", f[1]);

  return 0;
}

用\(f[i][j]\)表示剩下i粒瓜子和j瓣瓜子壳时期望多少次可以把瓜子拿完, \(f[0][j]=0\);

\(f[i][j] = \frac{i}{i+j}{f[i-1][j+2]} + \frac{j}{i+j}{f[i][j-1]}+1\)

答案: \(f[n][0]\)
复杂度: \(O(n^2\log{p})\)

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n;
LL f[2001][4001];
const int p = 998244353;
LL qmi(LL now, int k) {
  LL res = 1;
  for (; k; k >>= 1, now *= now, now %= p) {
    if (k & 1) {
      res *= now;
      res %= p;
    }
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= 2 * n - 2; j++) {
      f[i][j] = f[i - 1][j + 2] * i % p * qmi(i + j, p - 2) % p;
      ++f[i][j];
      if (j) f[i][j] += f[i][j - 1] * j % p * qmi(i + j, p - 2) % p;
    }
  }
  printf("%d\n", f[n][0]);

  return 0;
}

注意之前\(1\leq x \leq y \leq n\),这里\(1\leq {x,y} \leq n\)

之前概率dp做法不可以
比如

f[i]仍表示从x号城市出发期望经过多少条高速公路到达n号城市, f[n] = 0

拆解过程中有无限递归, 不满足无后效性

#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
vector<int> c[110];
LL f[110][110], v[110], a[110];
const int p = 1e9 + 7;
LL qmi(LL now, int k) {
  LL res = 1;
  for (; k; k >>= 1, now *= now, now %= p)
    if (k & 1) {
      res *= now;
      res %= p;
    }
  return res;
}

void Gauss() {
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      if (f[j][i]) {
        for (int k = i; k <= n; k++) {
          swap(f[i][k], f[j][k]);
        }
        swap(v[j], v[i]);
      }
    }
    for (int j = i + 1; j <= n; j++) {
      if (f[j][i]) {
        LL delta = f[j][i] * qmi(f[i][i], p - 2) % p;
        for (int k = i; k <= n; k++) {
          f[j][k] -= f[i][k] * delta % p;
          if (f[j][k] < 0) f[j][k] += p;
        }
        v[j] -= v[i] * delta % p;
        if (v[j] < 0) v[j] += p;
      }
    }
  }
  for (int i = n; i; i--) {
    for (int j = i + 1; j <= n; j++) {
      v[i] -= f[i][j] * a[j] % p;
      if (v[i] < 0) v[i] += p;
    }
    a[i] = v[i] * qmi(f[i][i], p - 2) % p;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    c[x].push_back(y);
  }
  for (int i = 1; i < n; i++) {
    f[i][i] = 1;
    v[i] = 1;
    int l = c[i].size();
    for (int j = 0; j < l; j++) f[i][c[i][j]] = p - 1 * qmi(l, p - 2);
  }
  f[n][n] = 1;
  Gauss();
  printf("%d\n", a[1]);

  return 0;
}

本栏目推荐文章
• 机器学习-概率图模型系列-隐含马尔科夫模型-33
• 机器学习-决策树系列-贝叶斯算法-概率图模型-29
• 概率生成函数（[CTSC2006] 歌唱王国 题解）
• CF1864H Asterism Stream【概率 DP，矩阵优化】
• 数学吧 《高中数学概率题》
• 概率霍夫变换（Progressive Probabilistic Hough Transform）原理详解
• 概率论复习笔记
• 为了降低个人股票投资者的决策误判概率，我们做了一款软件
• 概率论期末复习【更新中】
• 机器学习-线性分类-支持向量机SVM-合页损失-SVM输出概率值-16

概率概率论 概率qos 概率2.6 概率论 概率 概率 笔记 概率genshin 概率bug 概率 函数 概率 地址cdn 问题 硬币 概率