摘要：计数 dp，数位 dp，概率与期望 dp（+有后效性 dp）
计数 dp
OI-wiki 上讲的非常详细，推荐阅读。
计数类 dp 区别于求解最优解，此类问题需要统计 所有满足条件的可行解，而求解最优值的 dp 问题往往只需要统计子问题时满足不漏的条件即可，但是计数类 dp 需要满足 不重不漏 的条件，是约束更高的。
解此类问题一个重要的点就是如何划分子问题和确定数据排列的顺序，然后做到不重不漏，大部分情况下我们想到的方法，同一个解可能会被多次统计，这是不合理的。此类问题也常常与组合数结合到一起。
例题
求从 $(1,1)$ 到 $(n,m)$ 只能向右或向下且有 $k$ 个点不能经过（黑色点）的方案数。
$1\le n,m\le 10^{5}，1\le k\le 2000 $
如果所有的点都能经过，易得答案为：$C_{n+m-2}^{n-1}$，《进阶指南》 0x36,37 那一节有比较严谨的证明，
设 $f_i$ 表示原点到第 $i$ 个黑点的路径数量，
由减法原理得：原点到第 $i$ 个的点的路径数量为：$C_{x_i+y_i-2}^{x_i-1}-cnt_{pass\ by\ black\ dots}$。
由乘法原理得：第 $j$ 个黑点阻碍第 $i$ 个点的路径数为 $f_j\ast C_{x_i-x_j+y_i-y_j}^{x_i-x_j}$
由此可得状态转移方程：
$$f_i=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=0}^{i-1}f_j\ast C_{x_i-x_j+y_i-y_j}^{x_i-x_j},\ x_i\ge x_j,y_i\ge y_j$$
为了便于统计答案，我们设 $(n,m)$ 为第 $k+1$ 颗黑点。
需要注意的是 $j$ 枚举的是从左上角到 $(x_i,y_i)$ 经过的第 $1$ 个黑点，这样是为了保证不重不漏。
const int maxx =2e5+5;
const int maxn = 2022;
llt jc[maxx], inv[maxx];
pair<int, int> a[maxn];
int n, m, k, f[maxn];
llt Pow(llt a, int b) {
llt res = 1;
for ( ; b; b >>= 1, a = a * a % mod)
if (b & 1) res = res * a % mod;
return res;
}
int C(int n, int m) {
return jc[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
jc[0] = inv[0] = 1;
for (int i = 1; i <= maxx-5; i++) {
jc[i] = jc[i-1] * i % mod;
inv[i] = Pow(jc[i], mod - 2);
}
for (int i = 1; i <= k; i++) {
scanf("%d %d", &a[i].x, &a[i].y);
}
sort(a + 1, a + k + 1);
a[k+1] = make_pair(n, m);
for (int i = 1; i <= k + 1; i++) {
f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
for (int j = 1; j < i; j++) {
if (a[j].x <= a[i].x && a[j].y <= a[i].y) {
int z = C(a[i].x - a[j].x + a[i].y - a[j].y, a[i].x - a[j].x) % mod;
f[i] = (f[i] - 1ll*f[j] * z % mod + mod) % mod;
}
}
}
printf("%d\n", f[k+1]);
return 0;
}
多重集组合数：有 $n$ 种物品，第 $i$ 种有 $a_i$ 个。不同种类的物品可以互相区分但是相同的种类的无法区别。从这些物品中取 $m$ 个有多少种取法。
$1\le n,m,a_i\le 1000$
设 $f_{i+1,j}$ 从 前 $i$ 种物品中取出 $j$ 个的组合总数。
考虑暴力。我们可以把从 前 $i$ 种物品取 $j$ 个，划分为：从 前 $i−1$ 种物品中取 $j−k$ 个，从剩下的第 $i$ 种物品里取的 $k$ 个。则递推式可以表示为:
$$f_{i+1,j}=\sum_{k=0}^{\min(j,a_{i})}f_{i,j-k}$$
但是利用这个递推式进行计算的时间复杂度为 $O(nm^2)$，时间复杂度过高，进行优化。
分情况考虑：
Case 1. $a_i>j-1$
此时 $f_{i+1,j-1}$ 中 $k\in [0,j-1]$
$$f_{i+1,j-1}=f_{i,j-1}+f_{i,j-2}+\dots+f_{i,1}+f_{i,0}$$
由 $a_i>j-1$ 推得 $a_i\ge j$，此时 $k\in [0,j]$
$$f_{i+1,j}=f_{i,j}+f_{i,j-1}+f_{i,j-2}+\dots+f_{i,1}+f_{i,0}$$
可以发现两者只差一个 $f_{i,j}$，如图：
Case 2. $a_i\le j-1$
$$\begin{aligned}f_{i+1,j}&=f_{i,j}+f_{i,j-1}+\dots+f_{i,j-a_i}\\ f_{i+1,j-1}&=f_{i,j-1}+\dots+f_{i,j-1-a_i}\end{aligned}$$
最后得到递推式：
$$f_{i+1,j}=f_{i+1,j-1}+f_{i,j}-f_{i,j-1-a_i}$$
代码就不放了，因为我还没写。
数位 dp
没什么可讲的，直接上题。
例题
相邻两个数字之差至少为 $2$。
大家应该都做过，直接看代码回忆一下就行。
llt dfs(int pos, bool zro, bool lim, int lst) {
if (!pos) return 1;
if (!lim && f[pos][lst])
return f[pos][lst];
int lit = lim? num[pos] : 9;
llt res = 0;
for (int i = 0; i <= lit; i++)
if (abs(i-lst) >= 2) {
if (zro && !i)
res += dfs(pos-1, 1, lim && (i == lit), -7);
else
res += dfs(pos-1, 0, lim && (i == lit), i);
}
if (!lim && !zro)
f[pos][lst] = res;
return res;
}
求在 $[a,b]$ 中的所有整数中，每个数码各出现了多少次。
和上道题差不多，把 lst 换成 sum 就行了，
sum + ( ((!d)&&(!zro)&&(!i)) || (d&&(i==d)) )
设 $\text{sum}(i)$ 表示 $i$ 的二进制表示中 $1$ 的个数。给出一个正整数 $n$ ，求 $\prod_{i=1}^{n}\text{sum}(i)$。
$1\le n\le 10^{15}$
把十进制位改成二进制位，然后就没了。
llt dfs(int pos, bool lim, int sum) {
if (!pos) return max(sum, 1);
if (!lim && ~f[pos][sum])
return f[pos][sum];
int lit = lim ? num[pos] : 1;
llt res = 1;
for (int i = 0; i <= lit; i++)
res = res * dfs(pos-1, lim&&(i==lit), sum+(i==1)) % p;
if (!lim)
f[pos][sum] = res;
return res;
}
需要注意的是 f 数组的初始化，记忆化的答案可能为 0，所以初始化为 -1。
二进制表示中，$0$ 的数目不小于 $1$ 的数目 的数的个数。
llt dfs(int pos, bool zro, bool lim, int dif) {
if (!pos) return dif >= 32;
if (!lim && !zro && f[pos][dif])
return f[pos][dif];
int lit = lim? num[pos] : 1;
llt res = 0;
for (int i = 0; i <= lit; i++)
res += dfs(pos-1, zro && (!i), lim && (i==lit), dif+((i==0)?(zro?0:1):-1));
if (!lim && !zro)
f[pos][dif] = res;
return res;
}
号码中要出现至少 $3$ 个相邻的相同数字；
号码中不能同时出现 $8$ 和 $4$。
llt dfs (int pos, int left, int llft, int limit, int three, int four, int eight) {
if (four && eight) return 0;
if (pos <= 0) return three;
if (f[pos][left][llft][limit][three][four][eight])
return f[pos][left][llft][limit][three][four][eight];
llt sum = 0;
int upper = ! limit ? num[pos] : 9;
for (int i = 0; i <= upper; i++)
sum += dfs (pos-1,i,left,(limit||(i<upper)),(three||((i==left)&&(i==llft))),((i==4)||four),((i==8)||eight));
f[pos][left][llft][limit][three][four][eight] = sum;
return sum;
}
存在长度至少为 $2$ 的回文子串 的数 的个数
llt dfs (int pos, bool lim, bool zeo, bool can, int fst, int sec) {
if (!pos) return can;
if (!lim && !zeo) {
if (can && f[pos])
return f[pos];
else if (!can && g[pos][fst][sec])
return g[pos][fst][sec];
}
llt res = 0;
int upp = lim ? num[pos] : 9;
for (int i = 0; i <= upp; i++)
res += dfs (pos-1, lim&(i==num[pos]), zeo&!i, fst==i|sec==i|can, sec, (zeo&!i)?10:i) %mod,
res %= mod;
if (!lim && !zeo) {
if (can)
f[pos] = res;
else
g[pos][fst][sec] = res;
}
return res;
}
一般来说数位 dp 的正常难度是蓝，紫题一般是套上其他的东西 例如 AC 自动机，Tire 树，状压，组合数学，概率论，斜率优化，构造等，可以逝逝。
概率与期望 dp
众所周知：期望 dp 的期望得分是 0。
定义及性质
定义
若随机变量 $X$ 的取值有 $x_1,x_2,\dots$，一个随机事件可表示为 $X=X_i$，其概率 $P(X=X_i)=p_i$，则称 $E(x)=\sum p_ix_i$ 为随机变量 $X$ 的 数学期望。
通俗的讲，数学期望就是 随机变量取值与概率的乘积之和。
举个栗子：抛两枚骰子的期望（设随机变量 $X$ 表示抛一枚骰子的点数）
$$E(X)=\frac{1}{36}\ast 2+\frac{3}{36}\ast 3+\frac{4}{36}\ast 4+\dots+\frac{1}{36}\ast 12=7$$
性质
数学期望是线性函数，满足：
$$E(aX+bY)=a\ast E(X)+b\ast E(Y)$$
这条性质非常重要，是进行数学递推的基础。
还是上面那个例子，我们尝试用另一种方法求解：
设随机变量 $Y$ 表示抛一枚骰子的点数，其期望
$$E(Y)=\frac{1}{6}\ast 1+\frac{1}{6}\ast 2+\frac{1}{6}\ast 3+\dots+\frac{1}{6}\ast 6=3.5$$
根据上面的性质，我们可以得到：$E(X)=E(Y+Y)=3.5+3.5=7$
还有一些比较重要的性质，例如：
$$\begin{aligned}E(X+Y)&=E(X)+E(Y)\\ \\ E(X\ast Y)&=E(X)\ast E(Y)\end{aligned}$$
相关性质及证明：
E(aX+b)=aE(X)+b | E(X+Y)=E(X)+E(Y) | E(XY)=E(X)E(Y)
例题
概率 dp 主要用于求解期望、概率等题目，转移方程比较灵活。 一般求概率是正推，求期望是逆推。通过题目可以体会到这点。
原题面看了 10min 没看懂
给定一个物品数 $n$，每个物品都是无限个，每天你可以等概率获得一个物品。
给定 $q$ 组询问，每个询问给定一个值 $p$，问最少在多少天时集齐这 $n$ 个物品的概率大于 $\frac{p}{2000}$。
$1 \le n,p,q \le 1000$
设 $f_{i,j}$ 表示第 $i$ 天，取到了 $j$ 件不重复的物品的概率。
考虑转移：
由 $f_{i-1,j}$ 转移，因为是拿到重复物品才转移过来，所以：
$$f_{i,j}=f_{i-1,j}\ast\frac{j}{n}$$
由 $f_{i-1,j-1}$ 转移，表示拿到了不重复的物品，概率为 $\frac{n-j+1}{n}$，所以：
$$f_{i,j}=f_{i-1,j-1}\ast\frac{n-j+1}{n}$$
边界：$f_{0,0}=1$
这时候我们发现一个问题，我们不确定 dp 的第一维，也就是天数的上界是多少，
最简单的方法是测试极限数据，得到：$7274$。
还可以推柿子（by 皎月半洒花）：
$$\sum_{i=1}^{n}\frac{n}{n-i+1}$$
那么也就是调和级数 $n\cdot H(n)$，是 $O(n\ln n)$ 级别的，所以开 $1000\cdot \ln 1000$ 就好了。
可以二分，压维，但没必要。
牛牛要上 $n$ 个时间段的课，第 $i$ 个时间段在 $c_i$ 号教室，可以申请换到 $d_i$ 号教室，申请成功的概率为 $p_i$，至多可以申请 $m$ 节课进行交换。
第 $i$ 个时间段的课上完后要走到第 $i+1$ 个时间段的教室，给出一张图 $v$ 个教室 $e$ 条路，求最小的期望路程和。
$1 \leq n \leq 2000，0 \leq m \leq 2000，1 \leq v \leq 300，0 \leq e \leq 90000$。
涉及到最短路问题，考虑 Floyd。
换教室这一步本质上是状态的转移，即有 $p_i$ 的概率转移到 $d_i$，有 $1-p_i$ 的概率转移到 $c_i$，
再来考虑 dp 方程的设计，套路的，设 $f_{i,j,0/1}$ 表示在第 $i$ 个时间段连同之前交换过 $j$ 次，这个时间段换或不换的最小的期望路程和。
考虑转移：
此阶段不换，上一阶段不换
$$f_{i-1,j,0}+dis_{c_{i-1},c_{i}}$$
此阶段不换，上一阶段交换
$$f_{i-1,j,1}+dis_{d_{i-1},c_{i}} \ast p_{i-1}+dis_{c_{i-1},c_{i}} \ast (1-p_{i-1})$$
此阶段交换，上一阶段不换
$$f_{i-1,j-1,0}+dis_{c_{i-1},d_{i}}\ast p_i+dis_{c_{i-1},c_{i}}\ast(1-p_i)$$
此阶段交换，上一阶段交换
$$\begin{aligned}f_{i-1,j-1,1}+&dis_{c_{i-1},c_i}\ast(1-p_{i-1})\ast(1-p_i)\\ +&dis_{c_{i-1},d_i}\ast(1-p_{i-1})\ast p_i\\ +&dis_{d_{i-1},c_i}\ast (1-p_i)\ast p_{i-1}\\ +&dis_{d_{i-1},d_i}\ast p_{i-1}\ast p_i \end{aligned}$$
代码实现的话需要注意 double 别用 memset，QwQ。
求期望能掌握的每一段连续时刻的知识的喜爱程度之和是多少（需要注意的是，这里所说的连续时刻的知识不能被一段更长的所包含）。
$$ f(l,r)=a^{b(r-l)} \sum_{i=l}^r w_i$$
$0<n\le 10^5$
不难将题意转化为：
$$\sum_{l=1}^{n}\sum_{r=l}^{n}a^{b(r-l)}(1-p_{l-1})(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)$$
注意乘上 $l-1$，$r+1$ 不选的概率。
前缀和优化+暴力枚举时间复杂度 $O(n^2)$，
由数据范围可知正解的时间复杂度应是 $O(n)$ 或 $O(n\log n)$，
因此考虑单独枚举 $l$，递推求解后面的式子：
$$\sum_{l=1}^{n}(1-p_{l-1})\sum_{r=l}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)$$
简便起见，我们设：
$$\boxed{f_l=\sum_{r=l}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)}$$
考虑如何由 $f_{l+1}$ 推 $f_l$：
$$f_{l+1}=\sum_{r=l+1}^{n}a^{b(r-l-1)}(1-p_{r+1})\left(\prod_{i=l+1}^{r}p_{i}\right)\left(\sum_{i=l+1}^{r}w_{i}\right)$$
先乘上 $a^b\cdot p_l$：
$$f_{l+1}\cdot a^b\cdot p_l=\sum_{r=l+1}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l+1}^{r}w_{i}\right)$$
简便起见，我们设：
$$g_{l+1}=\sum_{r=l+1}^{n}a^{b(r-l-1)}(1-p_{r+1})\left(\prod_{i=l+1}^{r}p_{i}\right)$$
乘上 $a^b\cdot p_l\cdot w_l$ 并与上面的式子合并：
$$f_{l+1}\cdot a^b\cdot p_l+g_{l+1}\cdot a^b\cdot p_l\cdot w_l=\sum_{r=l+1}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)$$
再加上 $r=l$ 的情况：
$$g_l=g_{l+1}\cdot a^b\cdot p_l+p_{l}\cdot (1-p_{l+1})$$
所以
$$\boxed{f_{l+1}\cdot a^b\cdot p_l+g_{l}\cdot w_l=\sum_{r=l}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)}$$
由此我们得到了 $f$ 和 $g$ 的递推式：
$$f_l=f_{l+1}\cdot a^b\cdot p_l+g_{l}\cdot w_l$$
$$g_l=g_{l+1}\cdot a^b\cdot p_l+p_{l}\cdot (1-p_{l+1})$$
回归最初的式子，得到：
$$ans=\sum_{l=1}^{n}(1-p_{l-1})\cdot f_i$$
然后你就可以 $O(n)$ 解决这个问题了。
厚颜无耻打个广告，好像还在审 QwQ。
$n$ 个点，$m$ 条双向边。每一个城市的售票机有一个硬币投入时，机器会发一张从此城市到随机一个邻市的单程票。你需要从城市 $1$ 到城市 $n$。在每一个城市，当你买了一张票时，你可以选择立即使用它后到达目的地，或者是丢掉它并买一张新票。你可以无限制的购买的票。当你到达城市 $n$，旅行就会结束。
你需要确定一个满足以下条件的策略：
旅行最终到达终点的概率为 $1$。
花在旅行上的硬币的期望值越少越好。
求期望。
$1\le n,m\le 3\times 10^5$
非常套路的设 $f_u$ 为从 $u$ 到 $n$ 的期望最小时间。
考虑转移：
$$f_{u}=\frac{\sum_{(u,v)\in E}\min(f_u,f_v)}{deg_{u}}+1$$
$deg_{u}$ 表示 $u$ 点的度数。
发现不好直接转移，
但是我们可以确定：如果 $f_{v}<f_{u}$，那么 $f_v$ 一定会做出贡献，因此，可以开一个小根堆取最小值更新，因为当前的值是最小的，所以一定不会有其它的点可以影响它；
void dijkstra() {
q.push(make_pair(0, n));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (vis[v]) continue;
sum[v] += f[u];
tot[v] += 1;
f[v] = (sum[v] + deg[v]) / tot[v];
q.push(make_pair(-f[v], v));
}
}
}
傲娇少女幽香是一个很萌很萌的妹子，
给一个无向图 $G$，边权为 $[0,1]$ 间的实数（随机），求这个图的最小生成树的最大边权期望。
$1\le n\le 10,\ 1\le m\le n(n+1)/2$
tips: 对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\dots,x_n$，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$。
这个题是 @WeLikeStudying 推荐的，一看题解，wc，积分，默默的划掉了这道题，，，
后来发现不一定用积分，有加回来了，，
仔细看了看题解，发现不是凡人做的，就咕了，
有后效性 dp
这类问题基本上都是等概率走每条路，可以形成一个环，后面的状态会影响前面的状态，
可以用 高斯消元 做，部分题也能用多次 dp 卡过去。
例题
$n\ast m$ 的矩阵，现在在 $(x,y)$，每次等概率向左，右，下走或原地不动，但不能走出去，问走到最后一行期望的步数。
$1\le n,m\le10^3$
$$f_{i,j}=\begin{cases}\frac{1}{4}(f_{i,j}+f_{i+1,j}+f_{i,j-1}+f_{i,j+1})+1&\text{if } 1<j<m\\\frac{1}{3}(f_{i,j}+f_{i+1,j}+f_{i,j+1})+1&\text{if } j=1\\\frac{1}{3}(f_{i,j}+f_{i+1,j}+f_{i,j-1})+1&\text{if } j=m\end{cases}$$
简单整理一下：
$$\begin{aligned}3\ast f_{i,j}-f_{i+1,j}-f_{i,j+1}-f_{i,j-1}&=4\\2\ast f_{i,j}-f_{i+1,j}-f_{i,j+1}&=3\\2\ast f_{i,j}-f_{i+1,j}-f_{i,j-1}&=3\end{aligned}$$
然后就可以用 gauss 了。
然后你会发现时间复杂度不太对，是 $O(n^6)$，寄了，，
考虑递推，处理完第 $i+1$ 行之后，$f_{i+1,j}$ 成了常量，只用计算当前行就行了，并且你是知道 $f_{n,j}=0$ 的，所以这么做是没有问题的。
好，你成功将 $O(n^6)$ 优化成 $O(n^4)$，奆了，
但还是过不了，考虑优化 gauss，观察系数矩阵，我们会发现一个很有意思的情况：
$$\begin{bmatrix}2&-1&0&0&0&0\\-1&3&-1&0&0&0\\0&-1&3&-1&0&0\\0&0&-1&3&-1&0\\0&0&0&-1&3&-1\\0&0&0&0&-1&2\end{bmatrix}$$
那么我们可以考虑每次只操作三个元素：$g_{i,i},g_{i,i+1},g_{i,m+1}$，然后用这三个元素对第 $i-1$ 行操作；
然后从下向上扫一遍将其消为单位矩阵，这样的话我们每次 gauss 就是 $O(n)$，加上我们要操作 $n$ 行，然后就是 $O(n^2)$
毕竟是模板题，象征性的放一下代码。
double f[maxn][maxn], g[maxn][maxn];
int n, m, x, y;
void build(int i) {
g[1][1] = g[m][m] = 2;
g[1][2] = g[m][m-1] = -1;
g[1][m+1] = f[i+1][1] + 3;
g[m][m+1] = f[i+1][m] + 3;
for (int j = 2; j < m; j++) {
g[j][j-1] = g[j][j+1] = -1;
g[j][m+1] = f[i+1][j] + 4;
g[j][j] = 3;
}
}
void gauss() {
for (int i = 1; i <= m; i++) {
double k = g[i][i];
g[i][ i ] /= k;
g[i][i+1] /= k;
if (i != m) g[i][m+1] /= k;
k = g[i+1][i];
g[i+1][ i ] -= g[i][ i ] * k;
g[i+1][i+1] -= g[i][i+1] * k;
g[i+1][m+1] -= g[i][m+1] * k;
}
for (int i = m; i >= 1; i--) {
g[i-1][m+1] -= g[i-1][i] * g[i][m+1];
g[i-1][ i ] -= g[i-1][i] * g[i][ i ];
}
}
int main() {
scanf("%d %d\n%d %d", &n, &m, &x, &y);
if (m == 1) {
printf("%lf\n", (double)(n - x) * 2);
return 0;
}
for (int i = n - 1; i >= x; i--) {
build(i), gauss();
for (int j = 1; j <= m; j++) {
f[i][j] = g[j][m+1];
}
}
printf("%0.4lf\n", f[x][y]);
return 0;
}
无向连通图。 小 Z 随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以等概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。
$2\le n\le 500$，$1\le m\le 125000$
设 $f_i$ 表示第 $i$ 个点期望经过次数，对于 $1<i<n$ 有：
$$f_i=\sum_{(i,j)\in E,j\not=n}\frac{f_j}{deg_j}$$
对于 $1$ 有：
$$f_1=\sum_{(1,j)\in E,j\not=n}\frac{f_j}{deg_j}+1$$
因为 $n$ 点时就停止游走了，因此不考虑 $n$ 点的贡献。
因为存在环形结构，转移具有后效性看，所以对 $n-1$ 个 $f_i$ 进行高斯消元求解。
设 $g_i$ 表示第 $i$ 个边期望经过次数，对于 $E_i=(u,v),u\not=n,v\not=n$ 有：
$$g_i=\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$$
根据贪心的思想，期望经过次数多的边我们给它更小的编号。
struct edge {int u, v, nxt;} e[maxm];
int cnt, head[maxn], deg[maxn];
double a[maxn][maxn], g[maxm], ans;
int n, m;
void add(int u, int v) {
e[++cnt] = {u, v, head[u]}, head[u] = cnt;
deg[u]++;
}
void build() {
for (int u = 1; u < n; u++) {
a[u][u] = 1.0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v != n)
a[u][v] = -1.0 / deg[v];
}
}
a[1][n] = 1.0;
}
void Gauss() {
n--;
for (int i = 1; i <= n; i++) {
int p = i;
for (int j = i + 1; j <= n; j++)
if (fabs(a[j][i]) > fabs(a[p][i]))
p = j;
if (p != i)
for (int j = 1; j <= n + 1; j++)
swap(a[i][j], a[p][j]);
for (int j = 1; j <= n; j++)
if (i != j)
for (int k = i + 1; k <= n + 1; k++)
a[j][k] -= a[i][k] * a[j][i] / a[i][i];
}
for (int i = 1; i <= n; i++)
a[i][n+1] /= a[i][i];
n++;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v), add(v, u);
}
build(), Gauss();
for (int i = 1; i <= m; i++) {
int u = e[i << 1].u; if (u != n) g[i] += a[u][n] / deg[u];
int v = e[i << 1].v; if (v != n) g[i] += a[v][n] / deg[v];
}
sort(g + 1, g + m + 1);
for (int i = 1; i <= m; i++)
ans += g[i] * (m - i + 1);
printf("%0.3lf\n", ans);
return 0;
}
$k$ 维花园，$n_1∗n_2∗\dots∗n_k$，求从 $(1,1,1 … ,1)$ 到 $(n_1,n_2,\dots,n_k)$ 的期望时间。
有 $p$ 的概率，随机选取某一维，并向目的地走一步 （也就是该维坐标 $+1$ ，并且他不会走出花园）
有 $1−p$ 的概率，摔回走到当前位置的地方。（第 1s 不会有这种情况）
$T=5,\ k\le 5,\ n_i\le 1e5,\ p<1e9+7$
- 先放上官方“题解”：
设 $f[i]$ 表示 $i$ 到 $n+m$ 的期望步数。不难列出方程
$$fi=fi+1×p+fi−1×(1−p)$$
当前项只与前后项有关。 同时注意到， $f_1$ 没有前驱 ,$f_{n+m}$ 已知。因此 $f_1$ 实际上可以通过 $f_{n+m}$ 推出。这个推的过程呢，思想是将 $f_i$ 表示关于 $f_{i−1}$ 的一次多项式。 ($a∗fi−1 + b$ 的形式)显然 $f_{n+m}$ 是 $a=0,b=0$. 向前迭代即可。最后推出 $f_1$ 的 $a,b$ ，又因为这个 $a$ 实际上是没有意义的 （特别地， $1$ 的方程中没有前驱，并且向后的概率为 $1$ ），因此 $f_1=b$. 时间 $O(tkn \log)$ 。 $\log$ 是逆元。
非常锻炼阅读理解以及联系上下文推测语意的能力
- 再x两句出题人
然后就没了。