概率

某个事件 \(A\) 发生的可能性的大小，称之为事件 \(A\) 的概率，记作 \(P(A)\)。

• 假设某事的所有可能结果有 \(n\) 种，事件 \(A\) 涵盖其中的 \(m\) 种，那么 \(P(A)=m/n\)。
• 例如投掷一枚骰子，点数小于 \(3\) 的概率为 \(2/6=1/3\)。

如果两个事件A和B所涵盖的结果没有交集，那么 \(P\) ( \(A\) 或 \(B\) 发生) $ = P(A)+P(B)$。

还是掷骰子：

• \(P\) (点数小于 \(3\) 或点数大于 \(4\) ) \(= 2/6 + 2/6 = 2/3\)。
• 如果 \(A\) 和 \(B\) 所涵盖的结果有交集。
• 那么 \(P\) (\(A\) 或 \(B\) 发生) $ = P(A) + P(B) - P$ (\(A\) 与 \(B\) 同时发生)。
• \(P\) (点数小于 \(3\) 或点数为偶数) \(=2/6+3/6-1/6=2/3\)。

记事件 \(B\) 为“事件 \(A\) 不发生” :

• 那么 \(P(A)+P(B)=1\)，即 \(P(B)=1-P(A)\)。
• \(P\) (点数不小于 \(3\) ) \(=1-2/6=2/3\)。
• 在两个互不干扰的事中，事件 \(A\) 在其中一件事中，事件 \(B\) 在另外一件事中。
• 那么 \(P\) (\(A\) 与 \(B\) 同时发生) \(=P(A)*P(B)\)。
• 掷两个骰子，\(P\) (第一个点数小于 \(3\) 且第二个点数为偶数) \(=(2/6)*(3/6)=1/6\)。

期望

事件 \(A\) 有多种结果，记其结果的大小为 \(x\)，那么 \(x\) 的期望值表示 事件 \(A\) 的结果的平均大小，记作E(x)。

• \(E(x)=\) 每种结果的大小与其概率的乘积的和。
• 例如，记掷一枚骰子的点数为 \(x\)。
• \(E(x)=1 \times \dfrac{1}{6} +2 \times \dfrac{1}{6}+3 \times \dfrac{1}{6} + 4 \times \dfrac{1}{6} + 5 \times \dfrac{1}{6} + 6 \times \dfrac{1}{6} = \dfrac{7}{2}\)
• 若 \(c\) 为常数，那么：
• \(E(x+c)=E(x)+c，E(c \times x)=c \times E(x)\)。

因为如果我们把我们掷骰子掷出的点数统一加一个常数 \(c\)，再掷一次骰子，那么我们发现这样统计出来的期望正好是原先期望 \(+ c\)，乘法同理。

记两个事件的结果分别为 \(x\),\(y\)。

• \(E(x+y)=E(x)+E(y)\)。
• 例如：\(E\) (语文成绩 + 数学成绩)= \(E\) (语文成绩) + \(E\) (数学成绩)
• 若两个事件互相独立，\(E(x \times y) = E(x) \times E(y)\)。
• \(E\) (语文成绩 \(\times\) 数学成绩) \(= E\) (语文成绩) \(\times E\) (数学成绩)。

概率与期望的计算

概率与期望的计算有一个共同的计算技巧：

• 若事件所产生的所有方案都是等概率的，那么一些概率与期望即可转化为一个计数问题，算出后再除以总方案数即可。
• 如求事件符合条件 \(A\) 的概率，则转化为对符合 \(A\) 的 方案数的计数问题；若求方案的某种价值的期望值，则转化为所有方案的 价值总和的计数问题。
• 概率与期望的计算也经常用的其加法和乘法规则。
• 尤其是期望的加法规则，在期望的计算中十分常用。如求最大值与最小值之差的期望，则分别求二者的期望值再作差即可。
• 应用乘法规则时，要注意事件是否互相独立。

列方程法

概率与期望还可以通过列方程的方法计算。

有 \(4\) 张卡片，写着 \(0,1,2,3\)，每次抽出一张并放回，反复抽，抽出 \(0\) 为止。问抽取的次数的期望值 ：

• 设抽取次数为 \(x\)，则：
• \(x=1+x \times \dfrac{3}{4}\)。
• \(x=4\)。
• \(x=1+ x \times \dfrac{3}{4} + 0 \times \dfrac{1}{4}\)。

【钉子和小球】

【\(Description\)】

咕咕咕

【\(Solution\)】

首先我们看到小球在满钉子的情况下落在第 \(i\) 个格子中的概率 \(p_i = \dfrac{C_n ^ i}{2 ^ n} = \dfrac{n!}{2 ^ n i ! (n - i) !}\)

首先可以发现小球落在第一个位置的概率是 1，接着向下推，发现有两个性质 ：

• 如果小球下面有钉子，那么小球往两边滚动的概率是一样的，所以我们把上面的概率除以 2，平分到下面即可。
• 如果下面没有钉子，显然可以直接掉落到两格下面，直接转移即可。

换成 DP 来说就是 ：

设初始的 \(f[0][1].son 和 f[0][1].mu\) 为 1。
之后 \(n ^ 2\) 枚举转移，遇到钉子就 \(f[i][j] += \dfrac{f[i - 1][j]}{2}\)，否则 \(f[i + 1][j + 1] += f[i - 1][j]\)

因为每一层的钉子数不相同，所以从上面转移到下面的时候横坐标要加 1。

不过这种重载运算符我是真的不想写，一写就写错。

【\(Code\)】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long 
using namespace std;
const int Maxk = 1005;
int n,m;
int a[Maxk][Maxk];
inline int GCD(int x,int y) {return y == 0 ? x : GCD(y,x % y);}
struct Node{
  int x_,y_;
  void Gcd() {
    int k = GCD(x_,y_);
    x_ /= k;
    y_ /= k;
  }
  Node operator /(const int z) const {
    Node now = *this;
    now.y_ *= z;
    //cout << now.x_ << " " << now.y_ << endl;
    now.Gcd();
    return now;
  }
  Node operator +(Node now)const{
    if(x_ == 0) {
      now.Gcd();
      return now; 
    }
    Node th = *this;
    if(now.x_ == 0) {
      th.Gcd();
      return th;
    }
    int k = GCD(th.y_,now.y_);
    th.x_ *= (now.y_ / k);
    th.x_ += now.x_ * (th.y_ / k);
    th.y_ *= (now.y_ / k);
    th.Gcd();
    return th;
  }
}f[Maxk][Maxk]; 
inline int read()
{
  int f = 0,s = 0;char ch = getchar();
  while(!isdigit(ch)) f |= ch == '-',ch = getchar();
  while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48),ch = getchar();
  return f ? -s : s; 
} 
signed main()
{
  n = read(),m = read();
  for(int i = 1;i <= n;i ++) {//毒瘤的读入 
    for(int j = 1;j <= i;j ++) {
      char s;
      while((s = getchar()) != '*' && s != '.');
      if(s == '*') a[i][j] = 1;
    }
  }
  f[0][1].x_ = 1;
  f[0][1].y_ = 1;
  for(int i = 1;i <= n + 1;i ++) {
    for(int j = 1;j <= n + 1;j ++) {
      f[i][j].y_ = 1;
    }
  }
  for(int i = 1;i <= n;i ++) {
    for(int j = 1;j <= i;j ++) {//一行一列开始搜。 
      if(a[i][j]) {
        Node cur = f[i - 1][j];//这一行上面的钉子分向两边 
        cur = cur / 2;//概率除 2
        f[i][j] = f[i][j] + cur;
        f[i][j + 1] = f[i][j + 1] + cur;
      } 
      else {
        f[i + 1][j + 1] = f[i + 1][j + 1] + f[i - 1][j];
      } 
    } 
  }
  for(int i = 1;i <= n;i ++) {
    for(int j = 1;j <= i + 1;j ++) {
      f[i][j].Gcd();
    }
  }
  f[n][m + 1].Gcd();
  cout << f[n][m + 1].x_ << "/" << f[n][m + 1].y_ << endl; 
  return 0;
} 

---

期望DP

【\(Description\)】

小 \(Q\) 同学现在沉迷炉石传说不能自拔。他发现一张名为克苏恩的牌很不公平。

如果你不玩炉石传说，不必担心，小 \(Q\) 同学会告诉你所有相关的细节。炉石传说是这样的一个游戏，每个玩家拥有一个 \(30\) 点血量的英雄，并且可以用牌召唤至多 \(7\) 个随从帮助玩家攻击对手，其中每个随从也拥有自己的血量和攻击力。

小 \(Q\) 同学有很多次游戏失败都是因为对手使用了克苏恩这张牌，所以他想找到一些方法来抵御克苏恩。他去求助职业炉石传说玩家椎名真白，真白告诉他使用奴隶主这张牌就可以啦。

如果你不明白我上面在说什么，不必担心，小Q同学会告诉你他想让你做什么。

现在小 \(Q\) 同学会给出克苏恩的攻击力是 \(K\) ，表示克苏恩会攻击 \(K\) 次，每次会从对方场上的英雄和随从中随机选择一个并对其产生 \(1\) 点伤害。

现在对方有一名克苏恩，你有一些奴隶主作为随从，每名奴隶主的血量是给定的。如果克苏恩攻击了你的一名奴隶主，那么这名奴隶主的血量会减少 \(1\) 点，当其血量小于等于 \(0\) 时会死亡，如果受到攻击后不死亡，并且你的随从数量没有达到 \(7\) ，这名奴隶主会召唤一个拥有 $34 点血量的新奴隶主作为你的随从；

如果克苏恩攻击了你的英雄，你的英雄会记录受到 \(1\) 点伤害。你应该注意到了，每当克苏恩进行一次攻击，你场上的随从可能发生很大的变化。

小 \(Q\) 同学为你假设了克苏恩的攻击力，你场上分别有 \(1\) 点、 \(2\) 点、 \(3\) 点血量的奴隶主数量，你可以计算出你的英雄受到的总伤害的期望值是多少吗？

【\(Solution\)】

【\(Code\)】

【换教室】

【\(Description\)】

先咕着

【\(Solution\)】

【\(Code\)】

【奖励关】

好像没看懂。。。

【OSU！】

【\(Solution\)】

来推式子。

假设我们已经知道了前 \(x\) 个操作的期望值，现在来求第 \(x + 1\) 个 ：

\[(x + 1) ^ 3 \\= (x + 1)(x ^ 2 + 2x + 1) \\= x ^ 3 + x ^ 2 + 2x ^ 2 + 2x + x + 1 \\= x ^ 3 + 3x ^ 2 + 3x + 1 \]

于是我们发现每增加一个 1，我们的答案相比原答案多了 \(3x ^ 2 + 3x + 1\)。

所以我们可以来维护这个增加值的期望，并用递推的形式表现出来。

我们令 \(a[i]\) 为 \(x\) 的期望，\(b[i]\) 为 \(x ^ 2\) 的期望。

所以可以得到 ：

\[a[i] = (a[i - 1] + 1) \times s[i] \\ b[i] = (b[i - 1] + 2 \times a[i - 1] + 1) \times s[i] \]

所以最终的答案就是 \(ans[i] = ans[i - 1] + (3 \times b[i - 1] + 3 \times a[i - 1] + 1) \times s[i]\)。

我们的答案就是 \(ans[n]\)。

【\(Code\)】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
const int Maxk = 1e5 + 10;
int n;
double s[Maxk]; 
double a[Maxk],b[Maxk],ans[Maxk];
inline int read()
{
  int f = 0,s = 0;char ch = getchar();
  while(!isdigit(ch)) f |= ch == '-',ch = getchar();
  while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48),ch = getchar();
  return f ? -s : s;
}
signed main()
{
  n = read();
  for(int i = 1;i <= n;i ++) scanf("%lf",&s[i]);
  for(int i = 1;i <= n;i ++) {
    a[i] = (a[i - 1] + 1) * s[i];
    b[i] = (b[i - 1] + 2 * a[i - 1] + 1) * s[i];
    ans[i] = ans[i - 1] + (3 * (a[i - 1] + b[i - 1]) + 1) * s[i];
  }
  printf("%.1lf",ans[n]);
  return 0;
}