| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| C | 0 | 0 | 0 |
| D | 0 | 0 | 0 |
| E | 2 | 2 | 0 |
| H | 2 | 0 | 0 |
| J | 2 | 0 | 0 |
| M | 0 | 0 | 0 |
$$ \sum_{i=1}^n\sum_{j=1}^n {i+j\choose j}f(i+j,i)\\ f(i,j)= \begin{cases} 0, &i=0\\ a, &i=1\\ b\times f(i-1,j)+c\times f(i-2,j), &2\le i\le j\\ d\times f(i-1,j)+e\times f(i-2,j), &i\gt j \end{cases} $$
设
$$ A=\begin{pmatrix}b & 1 \\ c & 0\\ \end{pmatrix},B=\begin{pmatrix}d & 1 \\ e & 0\\ \end{pmatrix} $$
不难发现
$$ (f(i+j,i),f(i+j-1,i))=(a,0)A^{i-1}B^j $$
设 $S(i)=\sum_{j=1}^n {i+j\choose j}A^{i-1}B^j$，于是有
$$ \begin{equation}\begin{split} S(i+1)&=\sum_{j=1}^n {i+j+1\choose j}A^iB^j \\ &=\sum_{j=1}^n \left({i+j\choose j}+{i+j\choose j-1}\right)A^iB^j\\ &=AS(i)+\sum_{j=0}^{n-1}{i+j+1\choose j}A^{i}B^jB\\ & =AS(i)+\left(S(i+1)+A^i-{i+n+1\choose i+1}A^iB^n\right)B \end{split}\end{equation} $$ 移项，得 $$ S(i+1)=\left(AS(i)+A^iB-{i+n+1\choose i+1}A^iB^{n+1}\right)(E-B)^{-1} $$ 不难发现 $|E-B|=1-d-e\lt 0$，所以 $(E-B)$ 可逆。通过预处理上式可实现 $O(n)$ 递推。
给定 $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$ 后游戏结束。
问人物的期望收益，然后接下来两种修改操作，每次修改后再次询问人物收益：
数据保证 $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(v_k\to u)E(v_k)$，初始条件 $E(s)=1$。
于是上述方程可以表示成如下矩阵：
$$ \left[ \begin{array} {c c c c | c} 1&a_{1,2}&\cdots&a_{1,n-1}&p(1)\\ a_{2,1}&1&\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)$。