问题

给定一张无向图，每个时刻边权会由$(a,b)(a,b)$变为$(b,amodb)(b,a\; \backslash ;\; mod\; \backslash ;b)$，如果b为0则不变，点有点权。会以$\frac{p_i}{\sum p_k}\backslash frac\{p\_i\}\{\backslash sum\; p\_k\}$的概率选择i作为起点，每次会等概率选择，走到n结束。问期望经过的边的权值a的和。

有q次修改，每次修改可能修改点权或边权，修改点权的次数不会超过100.

题解

首先发现边权发生变化最多log次，可以单独处理完前log时间内的边权（阶段一），之后看作是一个不会变化的图上的随机游走（阶段二）。

这个时候考虑可以对于每条边计算其对答案的贡献。令$p[x]p[x]$表示阶段二中点$xx$期望被走过的次数。对于边$u,v,a,bu,v,a,b$那么阶段二产生的贡献即为$[u\mathrm{\ne }n]\frac{p_u}{de{g}_u}+[v\mathrm{\ne }n]\frac{p_v}{de{g}_v}[u\backslash neq\; n]\backslash frac\{p\_u\}\{deg\_u\}\; +\; [v\backslash neq\; n]\backslash frac\{p\_v\}\{deg\_v\}$,对于阶段一可以用类似的方法计算边产生的贡献。

p要怎么求？

$p_x=\sum \frac{p_{t{o}_x}}{de{g}_{t{o}_x}}+s{t}_{x}p\_\{x\}=\backslash sum\; \backslash frac\{p\_\{to\_x\}\}\{deg\_\{to\_x\}\}+st\_x$ 其中$s{t}_{x}st\_x$代表阶段一结束时，点在x的概率。

高斯消元即可

处理修改操作

对于边权的修改：因为统计答案的时候是采用计算边的贡献获得，可以减去原有的边权的贡献+新的边权的贡献得到答案。

复杂度:O(log A) （对于阶段一需要枚举时刻，阶段二直接计算，A代表边权的最大值）

对于点权的修改：因为高斯消元部分的系数矩阵不发生变化，可以记录下高斯消元操作的过程，使得之后每次修改点权都只多计算$O(n^2)O(n^2)$次

复杂度:$O(n^2+logA\cdot m)O(n^2+log\; A\backslash cdot\; m)$

总复杂度：$O(qlogA+n^3+nm\cdot logA)O(q\; log\; A+n^3+nm\backslash cdot\; log\; A)$ (操作一次数和n同规模)

吐槽

首先谢个罪，题面是我写的。Q数据范围没标实在是疏忽，辛苦选手满头问号的找了好几遍。

这题一看就是周老师的绝活，内榜熟悉的同学看了一眼就果断扔掉好评。和ccpc网络赛某道概率题有些像，有点改编的成分。

但这题为啥过的比B还多？我不理解（