Dyd's Blog

He who has a strong enough why can bear almost any how.

期望DP和概率DP

Posted on Edited on In
Symbols count in article: 12k Reading time ≈ 11 mins.

${\color{red} 快跑啊}$

期望DP和概率DP

概念

  • 随机变量：有多种可能值的变量，一般记为 $X$

  • 概率：一个事件发生的可能性，一般记为 $P(A)$ ，以下简记 $P(X==x_i)$ 为 $P(x_i)$

  • 期望：一个事件发生的概率乘上权值，记为 $E(X)$

  • 方差：用于描述一组数据的波动程度，记为 $Var(X)$ ，有
    $$
    Var(X)=\frac{\sum(x_i-\bar{x})}{n}
    $$

  • 依赖：一个随机变量 $X$ 的取值取决（或有关）于变量 $Y$ ，或者说在保证 $Y$ 发生的情况下发生 $X$ ，记为 $X|Y$ ，一下简记 $P(X==x_i|Y==y_i)$ 为 $P(x_i|y_i)$

  • 并：两个事件同时发生（即“且”），记为 $A\cap B$（也可以记为 $AB$ ）

  • 交：两个事件分别发生（即“或”），记为 $A\cup B$

  • 区分下列概念：

    $E(X)$ ：一个数，是 $x_i$ 的加权平均值；

    $E(X|Y)$ ：随机变量，关于 $Y$ 的函数，没有固定的 $y$ 值；

    $E(X|Y==y)$ ：一个数，是局限在 $\omega\in{\omega|Y(\omega)==y}$ 时， $X(\omega)$ 的取值的局部加权平均值

定理/公式

  • 对于两个独立事件 $A,B$ ，有：
    $$
    \begin{align}
    P(AB)=P(A)P(B)\\
    E(AB)=E(A)E(B)
    \end{align}
    $$
    正确性显然

  • 期望的线性性：

    （1）对于两个随机变量 $X,Y$ （可以相关），有：

    $$
    E(X+Y)=E(X)+E(X)
    $$

    证明：

    $$
    \begin{align}
    E(X+Y)
    &=\sum_{i}\sum_{j}P(X==i\wedge Y==j)\times(i+j)\\
    &=\sum_{i}\sum_{j}P(X==i\wedge Y==j)\times i+\sum_{i}\sum_{j}P(X==i\wedge Y==j)\times j\\
    &=\sum_{i}i\sum_{j}P(X==i\wedge Y==j)+\sum_{j}j\sum_{i}P(X==i\wedge Y==j)\\
    &=\sum_{i}iP(X==i)+\sum_{j}jP(Y==j)\\
    &=E(X)+E(Y)
    \end{align}
    $$

（2）对于一个常量 $C$ 有：
$$
E(CX)=CE(X)
$$

  • 前缀和技巧：对于离散变量（取值只有整数） $X$ ，有
    $$
    P(X==k)=P(X\le k)-P(X\le k-1)
    $$

  • 关于方差的性质:：

    （1）概率与方差的关系：
    $$
    \begin{align}
    Var(X)
    &=\frac{\sum_{i}(x_i-\bar{x})}{n}\\
    &=\sum_{i}\frac{(x_i-\bar{x})}{n}\\
    &=\sum_{x_k\in X}(x_k-\bar{x})P(x_k)
    \end{align}
    $$
    因为一个值出现的次数除以 $n$ 就是选它的概率

    （2）期望与方差的关系：

    首先，明显有 $\bar{x}=E(X)$ ，然后，我们再考虑对于一组数据 $X$ ，令 $y_i=(x_i-E(X))^2$ ，那么明显概率不变，有 $P(y_i)=P(x_i)$ ，则：
    $$
    \begin{align}
    E(Y)
    &=\sum_{y_k\in Y}y_kP(y_k)\\
    &=\sum_{x_k\in X}(x_k-E(X))^2P(x_k)\\
    &=Var(X)
    \end{align}
    $$
    故有：

    $$
    Var(X)=E((X-E(X))^2)
    $$

    （3）比较常用的一个性质：

    $$
    Var(X)=E(X^2)-E(X)^2
    $$

    需要注意 $E(X)=\bar{x}$ 是一个常数，故 $\sum2E(X)xP(x)=2E(X)\sum xP(x)=2E(X)^2$ ，另外谨记 $\sum P(x)=1$ ，则上述性质证明如下：
    $$
    \begin{align}
    Var(X)
    &=E((X-E(X))^2)\\
    &=E(X^2-2XE(X)+E(X)^2)\\
    &=E(X^2)-E(2XE(X))+E(E(X)^2)\\
    &=E(X^2)-\sum2E(X)xP(x)+\sum E(X)^2P(x)\\
    &=E(X^2)-2E(X)^2+E(X)^2\sum P(x)\\
    &=E(X^2)-2E(X)^2+E(X)^2\\
    &=E(X^2)-E(X)^2
    \end{align}
    $$

  • 全期望公式：
    $$
    E(E(X|Y))=E(X)
    $$
    证明如下：
    $$
    \begin{align}
    E(E(X|Y))
    &=\sum_{y}E(X|Y==y)P(y)\\
    &=\sum_{y}{\huge(}\sum_{x}xP(x|y){\huge)}P(y)\\
    &=\sum_{y}\sum_{x}xP(x|y)P(y)\\
    &=\sum_{y}\sum_{x}xP(y|x)P(x)\\
    &=\sum_{x}\sum_{y}xP(y|x)P(x)\\
    &=\sum_{x}xP(x){\huge(}\sum_{y}P(y|x){\huge)}\\
    &=\sum_{x}xP(x)\\
    &=E(X)
    \end{align}
    $$

  • 全概率公式：
    $$
    P(B)=\sum_{a_i\in A}P(a_i)P(B|a_i)
    $$

引入

对于一些比较难找到递推关系的数学期望问题，可以利用期望的定义式，根据实际情况以概率或者方案数（也就是概率乘总方案数）作为一种状态，而下标直接或间接对应了这个概率下的变量值，将问题变成比较一般的统计方案数问题或者利用全概率公式计算概率的递推问题

一般来说，概率DP找到正确的状态定义后，转移是比较容易想到的。但状态一定是“可数”的，把有范围的整数作为数组下标。事实上，将问题直接作为状态是最好的。如问“ $n$ 人做 $X$ 事的期望次数”，则设计状态为 $f[i]$ 表示 $i$ 个人做完事的期望。转移一般是递推，即从上一个状态转移得（填表）或转移向下一个状态（刷表），后者更为常用

有时期望DP需以最终状态为初始状态转移，即逆推。如 $f[i]$ 表示期望还要走 $f[i]$ 步到达终点，这种状态的转移是刷表法，形如 $f[i]=\sum p[i\rightarrow j]f[j]+w[i\rightarrow j]$ ，其中 $p[\ ]$ 表示转移的概率， $w[\ ]$ 表示转移对答案的贡献，一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推

还有些时候，要结合高斯消元来考虑

例题一

概率充电器

考虑算出每个点充电的概率 $P(i)$ ，利用期望的线性性， $\sum P(i)$ 就是答案

利用树形DP，考虑先求出每个点通过自己或是子树冲上电的概率，定为 $f[\ ]$ ，转移为
$$
\forall v\in son(u)\\
f[u]= f[u]+f[v]* P(v\rightarrow u)-f[u]* f[v]* P(v\rightarrow u)
$$
这里用了一个容斥：
$$
\begin{align}
P(A\cup B)\\
=P(A)+P(B)-P(AB)\\
=P(A)+P(B)-P(A)P(B)
\end{align}
$$
正确性显然：两个事件至少发生一个的概率就是分别发生的概率减去都发生的概率

然后再来考虑 $u$ 如何从父节点转移，转移方程类似于上面，但此时我们需要的是父节点不通过 $u$ 充上电的概率，令 $A$ 为“父节点不通过 $u$ 充上电”， $B$ 为“父节点通过 $u$ 充上电”，利用 $P(A)=\frac{P(A\cup B)-P(B)}{1-P(B)}$ 计算，注意特判 $P(B)==1$ 的情况

事时间复杂度 $O(n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define IL inline
using namespace std;
const int N = 500000 + 5;
const double E = 1e-7;
int n;
struct Edge
{
    int ne, ver;
    double p;
}e[N << 1];
int h[N], idx = 0;
double f[N], ans = 0;
IL void add(int x, int y, double z)
{
    e[idx].ver = y, e[idx].p = z, e[idx].ne = h[x], h[x] = idx++;
}
IL void dp(int x, int fa)
{
    for (int i = h[x], y; i != -1; i = e[i].ne)
    {
        y = e[i].ver;
        if (y == fa)
            continue;
        dp(y, x);
        f[x] = f[x] + f[y] * e[i].p - f[x] * f[y] *e[i].p;
    }
}
IL void dp2(int x, int fa)
{
    for (int i = h[x]; i != -1; i = e[i].ne)
    {
        if (e[i].ver == fa)
            continue;
        double pa, pb;
        pb = f[e[i].ver] * e[i].p;
        if (pb + E > 1 && pb - E < 1)
            dp2(e[i].ver, x);
        else
        {
            pa = (f[x] - pb) / (1 - pb);
            f[e[i].ver] = f[e[i].ver] + pa * e[i].p - f[e[i].ver] * pa *e[i].p;
            dp2(e[i].ver, x);
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i <= n; ++i)
        h[i] = -1;
    for (int i = 1, x, y, z; i < n; ++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, (double)z / 100.0), add(y, x, (double)z / 100.0);
    }
    for (int i = 1, q; i <= n; ++i)
        scanf("%d", &q), f[i] = (double)q / 100.0;
    dp(1, -1);
    dp2(1, -1);
    for (int i = 1; i <= n; ++i)
        ans += f[i];
    printf("%.6lf\n", ans);
    return 0;
}

例题二

亚瑟王

依旧利用期望的线性性，考虑求出每张卡被出掉的概率，不难发现，一张卡被出的概率与被经过的次数有关，于是设 $f[i][j]$ 表示 $r$ 轮后，前 $i$ 张卡被选了 $j$ 张的概率，那么 $f[i-1][j]$ 就是 $i$ 被考虑 $r-j$ 次的概率（因为还有 $r-j$ 张在 $i$ 及以后的牌中选），于是 $i$ 被选到的概率为 $\sum_{j>0}f[i-1][j]\times(1-(1-p[i])^{r-j})$ ，则转移就是枚举选不选 $i+1$
$$
\begin{align}
&\text{选：}\\
&f[i + 1][j + 1]+=f[i][j]* (1-(1-p[i+1])^{r-j})\\
&\text{不选：}\\
&f[i + 1][j]+=f[i][j]* (1-p[i+1])^{r-j}\\
\end{align}
$$
时间复杂度 $O(Tnr)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define IL inline
using namespace std;
const int N = 220 + 5;
struct Card
{
    double p, d;
} a[N];
double f[N][N], ans;
IL double qpow(double x, int y)
{
    double res = 1;
    while (y)
    {
        if (y & 1)
            res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}
int main()
{
    int T;
    scanf("%d", &T);
    int n, r;
    while (T--)
    {
        scanf("%d%d", &n, &r);
        for (int i = 1; i <= n; ++i)
            scanf("%lf%lf", &a[i].p, &a[i].d);
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= r; ++j)
                f[i][j] = 0;
        f[0][0] = 1, ans = 0;
        double _t;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= min(i, r); ++j)
            {
                _t = qpow(1 - a[i + 1].p, r - j);
                f[i + 1][j] += f[i][j] * _t;
                if (j < r)
                {
                    f[i + 1][j + 1] += f[i][j] * (1 - _t);
                    ans += f[i][j] * (1 - _t) * a[i + 1].d;
                }
            }
        printf("%.10lf\n", ans);
    }
    return 0;
}

例题三

游走

明显，被经过次数多的边编号要小，这启发我们去求每条边期望被经过的次数，但 $m$ 的范围过大，直接求时间复杂度无法接受，于是考虑将边的期望转换为点的期望

设 $du[i]$ 表示第 $i$ 个点的度， $f[i]$ 表示它的期望经过次数，则有有个鬼啊，我想不到啊！！！ ：

$$
f[i]=
\begin{cases}
&\sum_{(i,j)\in E,j\ne n}\frac{f[j]}{du[j]}+1&i=1\\
&\sum_{(i,j)\in E,j\ne n}\frac{f[j]}{du[j]}&1<i<n
\end{cases}
$$

需要注意：到 $n$ 点就停止了，所以不考虑从 $n$ 转移过来

那么第 $i$ 条边的期望经过次数 $g[i]$ 就是
$$
\begin{align}
&g[i]=\frac{f[u]}{du[u]}+\frac{f[v]}{du[v]}&E_i=(u,v),u\ne n,v\ne n
\end{align}
$$
那么只需求出 $f$ 就好了，然鹅，由于是DAG，转移的顺序无法解决（怎么转都有后效性），所以，高斯消元解决不会就和我一样愣着吧

超级毒瘤的代码我尽量标准化了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define IL inline
using namespace std;
const int N = 500 + 5, M = 125000 + 5;
const double eps = 1e-12;
int n, m;
struct Matrix
{
    double x[N][N];
} a;
struct Edge
{
    int ne, from, ver;
} e[M << 1];
int h[N], idx = 2;
int du[N];
double g[M], ans = 0;
IL void add(int x, int y)
{
    e[idx].from = x, e[idx].ver = y, e[idx].ne = h[x], h[x] = idx++;
}
IL int gauss(Matrix &x, int _n)
{
    int c, r, _t;
    for (c = 1, r = 1; c <= _n; ++c)
    {
        _t = r;
        for (int i = r; i <= _n; ++i)
            if (fabs(x.x[i][c]) > fabs(x.x[_t][c]))
                _t = i;
        if (fabs(x.x[_t][c]) < eps)
            continue;
        for (int i = c; i <= _n + 1; ++i)
            swap(x.x[_t][i], x.x[r][i]);
        for (int i = _n + 1; i >= c; --i)
            x.x[r][i] /= x.x[r][c];
        for (int i = r + 1; i <= _n; ++i)
            if (fabs(x.x[i][c]) > eps)
                for (int j = _n + 1; j >= c; --j)
                    x.x[i][j] -= x.x[r][j] * x.x[i][c];
        ++r;
    }
    if (r <= _n)
    {
        for (int i = r; i <= _n; ++i)
            if (fabs(x.x[i][_n + 1]) > eps)
                return -1;
        return 0;
    }
    for (int i = _n; i >= 1; --i)
        for (int j = i + 1; j <= _n; ++j)
            x.x[i][_n + 1] -= x.x[i][j] * x.x[j][_n + 1];
    return 1;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; ++i)
        h[i] = -1;
    for (int i = 1, u, v; i <= m; ++i)
    {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
        ++du[u], ++du[v];
    }
    --n; // 构建矩阵时注意第n个点不转移,所以只有n-1个点
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n + 1; ++j)
            a.x[i][j] = 0;
    for (int i = 1; i <= n; ++i)
    {
        a.x[i][i] = 1.0;
        for (int j = h[i], k; j != -1; j = e[j].ne)
        {
            k = e[j].ver;
            if (k == n + 1)
                continue;
            a.x[i][k] = -1.0 / du[k];
        }
    }
    a.x[1][n + 1] = 1;
    gauss(a, n);
    for (int i = 1, u, v; i <= m; ++i)
    {
        u = e[i << 1].from;
        v = e[i << 1].ver;
        g[i] = a.x[u][n + 1] / du[u] + a.x[v][n + 1] / du[v];
    }
    sort(g + 1, g + 1 + m);
    ans = 0;
    for (int i = 1; i <= m; ++i)
        ans += g[i] * (m - i + 1);
    printf("%.3lf", ans);
    return 0;
}

例题四

最后来看一道毒瘤题

Slay the Spire

贪心策略

明显，得排个序，由于强化卡的数字至少为 $2$ ，在可以打出的 $k$ 张牌中，尽可能多的打强化卡可以使伤害最大化（当然，至少得剩下一张攻击牌，不然没伤害）

另一个方面，根据期望的线性性（又是它），期望造成的伤害等于强化牌的期望乘积乘上攻击牌的期望和（好乱），而答案乘了一个奇奇怪怪的东西后分母没了，分子的化其实就是方案数乘价值

dp方程设计

如此，答案就跟强化牌和攻击牌分别独立相关，这启发我们分开计算：令 $f[i][j][0]$ 表示在前 $i$ 张强化牌中取 $j$ 张且第 $i$ 张被选的选法的乘积之和， $f[i][j][1]$ 表示前 $i$ 张强化牌中取 $j$ 张（不管选没选 $i$ ）的乘积之和，令 $g[i][j][0]$ 表示在前 $i$ 张攻击牌中取 $j$ 张且第 $i$ 张被选的选法的和之和， $f[i][j][1]$ 表示前 $i$ 张强化牌中取 $j$ 张（不管选没选 $i$ ）的和之和

可以看到上面的定义非常的痛苦，所以好心的我在这里写点提示：

  1. 为什么要强迫选第 $i$ 张呢？这是因为讨厌的九条可怜是随机选的卡，若不保证选了第 $i$ 张，统计答案时会有重复（或者不好统计）
  2. 为啥都是个…之和呢？这是因为最后算的是期望（当然，它乘了个玄学的东西把分母弄没了），期望本身就该算和
  3. 那为啥还要定一个不管选没选 $i$ 的情况呢？其实是为了方便求出强迫选的情况，换句话说，是当辅助的，而在统计答案时我们也靠它们可以去掉一个循环

如果理解了以上定义（没理解就看看下面的转移和统计答案辅助理解一下），则可以发现转移方程如下（ $a$ 是强化牌， $b$ 是攻击牌）：
$$
\begin{align}
&f[i][j][0]=a[i]\times f[i-1][j-1][1]\\
&f[i][j][1]=f[i][j][0]+f[i-1][j][1]\\
&g[i][j][0]=b[i]\times \binom{i-1}{j-1}+g[i-1][j-1][1]\\
&g[i][j][1]=g[i][j][0]+g[i-1][j][1]
\end{align}
$$
需要注意的是， $g[i][j][0]$ 的转移中， $\binom{i-1}{j-1}$ 表示在 $i-1$ 个数中选择 $j-1$ 个数的方案，即从 $g[i-1][j-1][1]$ 转移到 $g[i][j][0]$ 共有 $\binom{i-1}{j-1}$ 种情况，而每种情况卡牌权值和加上了 $b[i]$

预处理组合数，推得 $f,g$ 都可以在 $O(n^2)$ 内解决

统计答案

来看看如何计算答案！分类讨论！

  • 若抽出来的 $m$ 张牌中，强化牌的数量少于 $k-1$

    此时当然是把强化牌全出了，然后攻击牌从大到小依次出，可以枚举 $i,j$ 表示被选中的强化牌有 $i$ 张，最后一张被选中的攻击牌是第 $j$ 张

    在强化牌中选择 $i$ 张的所有合法情况下的乘积之和，其实就是 $f[n][i][1]$

    而强化牌中选择 $i$ 张，攻击牌中就要选择 $k-i$ 张，又由于最后被选中的攻击牌是第 $j$ 张，所以所有合法情况下攻击牌的和之和，其实就是 $g[j][k-i][0]$

    但不要忘了，九条她的 $m$ 张牌是随机选的！为了保证最后打出的 $k$ 张牌是我们要的 $k$ 张牌，则剩余的 $m-k$ 张牌要满足不存在强化牌且攻击牌都要排在第 $j$ 张牌的后面（这也是我们必须要枚举 $j$ 的原因），因此共有 $\binom{n-j}{m-k}$ 种方案

    总之，对于这种情况，我们枚举 $i,j$ ，每次答案加 $f[n][i][1]\times g[j][k-i][0]\times\binom{n-j}{m-k}$

  • 若抽出来的 $m$ 张牌中，强化牌的数量大于等于 $k-1$

    此时我们选则出积最大的 $k-1$ 张强化牌，再乘上一张最大的攻击牌，可以枚举 $i,j$ 表示最后一张被选中的强化牌是第 $i$ 张，被选中的攻击牌是第 $j$ 张

    在前 $i$ 张强化牌中选 $k-1$ 张，且必选第 $i$ 张，其实就是 $f[i][k-1][0]$

    在攻击牌中选了第 $j$ 张，权值就是 $g[j][1][0]=b[j]$

    和上面一样，由于是随机选牌，剩余的 $m-k$ 张牌要满足强化牌都要排在第 $i$ 张牌的后面且攻击牌都要排在第 $j$ 张牌的后面，有 $\binom{2n-i-j}{m-k}$ 种方案

    总之，对于这种情况，我们枚举 $i,j$ ，每次答案加 $f[i][k-1][0]\times b[j]\times\binom{2n-i-j}{m-k}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define IL inline
using namespace std;
const int N = 3000 + 5, P = 998244353;
int n, m, k;
int a[N], b[N];
int C[N][N];
int f[N][N][2], g[N][N][2];
int ans;
IL bool cmp(int x, int y)
{
    return x > y;
}
IL void pred()
{
    C[0][0] = 1;
    for (int i = 1; i < N; ++i)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
}
int main()
{
    pred(); //处理C
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        ans = 0;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &b[i]);
        sort(a + 1, a + 1 + n, cmp), sort(b + 1, b + 1 + n, cmp);
        //处理f
        f[0][0][0] = f[0][0][1] = 1;
        for (int i = 1; i <= n; ++i)
        {
            f[i][0][1] = 1;
            for (int j = 1; j <= i; ++j)
            {
                f[i][j][0] = (LL)a[i] * f[i - 1][j - 1][1] % P;
                f[i][j][1] = (f[i][j][0] + f[i - 1][j][1]) % P;
            }
        }
        //处理g
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
            {
                g[i][j][0] = ((LL)b[i] * C[i - 1][j - 1] + g[i - 1][j - 1][1]) % P;
                g[i][j][1] = (g[i][j][0] + g[i - 1][j][1]) % P;
            }
        //情况1
        for (int i = 0; i < k - 1; ++i)
            for (int j = 1; j <= n; ++j)
                ans = ((LL)f[n][i][1] * g[j][k - i][0] % P * C[n - j][m - k] + ans) % P;
        //情况2
        for (int i = 0; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                ans = ((LL)f[i][k - 1][0] * b[j] % P * C[2 * n - i - j][m - k] + ans) % P;
        printf("%d\n", ans);
    }
    return 0;
}

废话

啊啊啊我太弱了！同机房的 ${\Huge{\color{Red}\mathfrak{dalao}}}$ 天天嘲笑我/(ㄒoㄒ)/~~

啊啊啊啊怎么办要被自己菜死了！┏┛墓┗┓…(((m -__-)m