首页 > 其他分享 >概率dp

概率dp

时间：2023-12-21 19:14:11浏览次数：27  
标签：now 概率 int res LL 110 include dp

概率dp

image.png

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

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

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

能走到y号城市的概率

\[f[y] = \sum_{x\in pre(y)}{\frac{f[x]}{d[x]}} \]

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;
}

image.png

最简分数\(\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;
}

image.png

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

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

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

\[f[i][j] = \sum_{x\in pre(i)}{\frac{f[x][j-1]}{d[x]}} \]

答案:\(\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;
}

image.png

用\(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;
}

image.png

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

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

\[1\leftrightarrows 2 \rightarrow 3 \]

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

\[ \]

\[\begin{array}{l} f[1] = f[2] + 1 \\ f[2] = \frac{1}{2}{f[1]} + \frac{1}{2}{f[3]} \end{array} \]

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

#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;
}

标签：now,概率,int,res,LL,110,include,dp
From： https://www.cnblogs.com/viewoverlooking/p/17919905.html

相关文章

  • 状压dp
    状压dp暴力枚举每一天摸不摸鱼,对于每一组方案,我们都可以判断其可不可行,从可行方案中选择快乐值总和最大的一组;复杂度\(O(2^{20})\)每一组方案可以用一个长度为n的二进制串来表示;从右到左第i个位置表示第i天摸不摸鱼(1表示,0表示不摸)当n=5时,10111表示在1,2,......
  • k8s~ingress_service_endpoint_pod四壮士
    在Kubernetes中，Service和Endpoints是两个重要的概念，它们之间存在着密切的关系。Service：Service是Kubernetes中用于定义一组Pod的访问方式的抽象。通过创建Service，可以为一组具有相同标签的Pod提供统一的访问入口，使得客户端可以通过Service来访问这些Pod，而无需了解其具体的IP地......
  • class080 状压dp-上【算法】
    class080状压dp-上【算法】算法讲解080【必备】状压dp-上Code1464.我能赢吗//我能赢吗//给定两个整数n和m//两个玩家可以轮流从公共整数池中抽取从1到n的整数（不放回）//抽取的整数会累加起来（两个玩家都算）//谁在自己的回合让累加和>=m，谁获胜//若先出手的玩家能稳赢则......
  • class081 状压dp-下【算法】
    class081状压dp-下【算法】算法讲解081【必备】状压dp-下Code11434.每个人戴不同帽子的方案数//每个人戴不同帽子的方案数//总共有n个人和40种不同的帽子，帽子编号从1到40//给你一个整数列表的列表hats，其中hats[i]是第i个人所有喜欢帽子的列表//请你给每个人......
  • class073 背包dp-01背包、有依赖的背包【算法】
    class073背包dp-01背包、有依赖的背包【算法】算法讲解073【必备】背包dp-01背包、有依赖的背包code1P1048[NOIP2005普及组]采药//01背包(模版)//给定一个正数t，表示背包的容量//有m个货物，每个货物可以选择一次//每个货物有自己的体积costs[i]和价值values[i]//返回在......
  • class074 背包dp-分组背包、完全背包【算法】
    class074背包dp-分组背包、完全背包【算法】算法讲解074【必备】背包dp-分组背包、完全背包code1P1757通天之分组背包//分组背包(模版)//给定一个正数m表示背包的容量，有n个货物可供挑选//每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)//同一个组的物品只......
  • 线性DP
    线性DP例题：POJ2279思考：考虑dp_{i,j,k}表示第i行，第j列，安排k去站的方案数。错误原因：安排k去站但是可能会造成重复选择k。正解：考虑dp_{a1,a2,a3,a4,a5}表示各排从左边起分别站了a1,a2,a3,a4,a5个人时，合影方案数。疑惑：Q1.为什么不用考虑某个位置究竟站的......
  • Flink处理函数解析（ProcessFunction和KeyedProcessFunction）
    Flink中的处理函数（ProcessFunction和KeyedProcessFunction）在对于数据进行颗粒化的精确计算时使用较多，处理函数提供了一个定时服务（TimerService），可以向未来注册一个定时服务，我们可以把它理解为一个闹钟，当闹钟响起时，就调用ProcessFunction中的onTimer()方法，会对数据进行一些计算。我......
  • 金牌导航-数据结构优化DP
    数据结构优化DP例题A题解设\(f_{i,j}\)表示以第\(i\)位为结尾，长度为\(j\)的严格单调上升子序列的数量。那么显然有\(f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}\times(a_k<a_i)\)然后发现这玩应\(O(n^2m)\)直接寄掉了。考虑优化。发现只有当\(a_k<a_i\)时才会有贡献。......
  • TQX 的 DP AAgain！
    闲话：这确实抽象，将所有人给干离线了……不如叫做TQX的离线DPQwQDP基本思路就是找一个比较好的能够描绘问题的状态,想怎么转移,再进行优化。--TQX背包DPloj6089.小Y的背包计数问题根号分治优化背包，大概就是利用\(cnt\timessiz\gecap\)将多重变为完全，然后统......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99