这是本文档旧的修订版！
目录
J. Random Walk
题意
给定 $n$ 个点，$m$ 条边，每条边两个权值 $(a_i,b_i)$，在 $t$ 时刻经过第 $i$ 条边的收益为 $\max(\lfloor\frac {a_i}{2^t}\rfloor,b)$，且一条边经过多次收益也计算多次。
每个点一个点权 $w_i$，起点位于点 $i$ 的概率为 $\cfrac{w_i}{\sum_{i=1}^{n-1} w_i}$。每个时间单位人物从当前点等概率移动到相邻点，且移动到点 $n$ 后游戏结束。
问人物的期望收益，然后接下来两种修改操作，每次修改后再次询问人物收益：
- 将某条边 $(u,v)$ 的边权修改为 $(a,b)$，保证这条边原图中存在
- 将某个点的 $w_i$ 修改
数据保证 $1\le b_i\le a_i\le 100$，且第二类修改操作不超过 $n$ 个。
题解
设 $\text{dp}(u,i)$ 表示 $t=i$ 时人物位于点 $u$ 的概率，$E(u)$ 表示人物经过点 $u$ 的期望次数，$G(u)$ 表示与 $u$ 相邻的边，$p(u)=\cfrac{w_i}{\sum_{i=1}^{n-1} w_i}$。
不难发现 $t\ge 6$ 后每条边收益一定等于 $b_i$，于是答案等于
$$ \sum_{u=1}^{n-1}\frac 1{\deg(u)}\sum_{e_i\in G(u)}\sum_{t=0}^{+\infty}\max(\lfloor\frac {a_i}{2^t}\rfloor,b_i)\text{dp}(u,t)=\sum_{u=1}^{n-1}\frac 1{\deg(u)}\sum_{e_i\in G(u)}\left(b_i\left(E(u)-\sum_{t=0}^5\text{dp}(u,t)\right)+\sum_{t=0}^5\max (\lfloor\frac {a_i}{2^t}\rfloor,b_i)\text{dp}(u,t)\right) $$
关于 $\text{dp}(u,t)(0\le t\le 5)$，可以 $O(6m)$ 暴力计算，接下来考虑计算 $E(u)$。
考虑建立有向图，如果原图中边 $(u,v)$ 满足 $u,v\neq n$，则连边 $u\to v(w=\frac 1{\deg (u)}),v\to u(w=\frac 1{\deg (v)})$。
否则，假设 $v=n$，则只连边 $u\to v(w=\frac 1{\deg (u)})$。同时建立超级源点 $s$，连边 $s\to u(w=p(u))$。
对每个点 $u$，考虑所有入边 $v_1\to u,v_2\to u\cdots v_k\to u$，不难发现 $E(u)=\sum_{i=1}^k w_kE(v_k)$，初始条件 $E(s)=1$。
于是上述方程可以表示成如下矩阵：
$$ \left[ \begin{array} {c c c c | c} %这里的c表示数组中元素对其方式：c居中、r右对齐、l左对齐，竖线表示2、3列间插入竖线 1&a_{1,2}&\cdots&a_{1,n-1}&p(1)\\ 1&a_{2,2}&\cdots&a_{2,n-1}&p(2)\\ \vdots&\vdots&\ddots&\vdots\\ a_{n-1,1}&a_{n-1,2}&\cdots&1&p(n-1)\\ \end{array} \right] $$
$O(n^3)$ 即可计算出所有 $E(u)$，因此计算初始答案复杂度为 $O(n^3+6m)$。
接下来考虑修改操作，发现第一种修改操作对 $\text{dp}(u,t),E(u)$ 均无影响，如果 $u\neq n$，对答案影响为
$$ \frac 1{\deg(u)}\left(b_i\left(E(u)-\sum_{t=0}^5\text{dp}(u,t)\right)+\sum_{t=0}^5\max (\lfloor\frac {a_i}{2^t}\rfloor,b_i)\text{dp}(u,t)\right) $$
同理 $v\neq n$ 时也产生类似影响，因此单次处理复杂度 $O(6)$。
第二种操作对 $\text{dp}(u,t),E(u)$ 均产生影响，同样 $\text{dp}(u,t)$ 可以暴力计算，但 $E(u)$ 重新计算成分过高。
注意到 $E(u)$ 的增广矩阵仅有增广部分被修改，因此可以预处理出原矩阵的逆 $A^{-1}$，则有
$$ \begin{pmatrix} E(1)\\ E(2)\\ \vdots\\ E(n-1)\\ \end{pmatrix} = A^{-1} \begin{pmatrix} p(1)\\ p(2)\\ \vdots\\ p(n-1)\\ \end{pmatrix} $$
因此可以 $O(n^2+6m)$ 重新计算一次答案。总时间复杂度 $O(n^3+6nm+6q)$。
