2020-2021:teams:legal_string:组队训练比赛记录:contest17
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest17 [2021/08/31 22:17] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest17 [2021/09/05 10:20] (当前版本) jxm2001 [题意] |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| | C | 0 | 0 | 0 | | | C | 0 | 0 | 0 | | ||
| | D | 0 | 0 | 0 | | | D | 0 | 0 | 0 | | ||
| - | | E | 2 | 0 | 0 | | + | | E | 2 | 2 | 0 | |
| | H | 2 | 0 | 0 | | | H | 2 | 0 | 0 | | ||
| | J | 2 | 0 | 0 | | | J | 2 | 0 | 0 | | ||
| 行 18: | 行 18: | ||
| $$ | $$ | ||
| - | \sum_{i=1}^n\sum_{j=1}^n {i+j\choose j}f(i,j)\\ | + | \sum_{i=1}^n\sum_{j=1}^n {i+j\choose j}f(i+j,i)\\ |
| f(i,j)= | f(i,j)= | ||
| \begin{cases} | \begin{cases} | ||
| 行 40: | 行 40: | ||
| $$ | $$ | ||
| - | (f(i+j,j),f(i+j-1,j))=(a,0)A^{i-1}B^j | + | (f(i+j,i),f(i+j-1,i))=(a,0)A^{i-1}B^j |
| $$ | $$ | ||
| 行 48: | 行 48: | ||
| \begin{equation}\begin{split} | \begin{equation}\begin{split} | ||
| S(i+1)&=\sum_{j=1}^n {i+j+1\choose j}A^iB^j \\ | 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\\ | + | &=\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\choose j}A^{i-1}B^jB\\ | + | &=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 | & =AS(i)+\left(S(i+1)+A^i-{i+n+1\choose i+1}A^iB^n\right)B | ||
| \end{split}\end{equation} | \end{split}\end{equation} | ||
| 行 209: | 行 209: | ||
| 否则，假设 $v=n$，则只连边 $u\to v(w=\frac 1{\deg (u)})$。同时建立超级源点 $s$，连边 $s\to u(w=p(u))$。 | 否则，假设 $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$。 | + | 对每个点 $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} %这里的c表示数组中元素对其方式：c居中、r右对齐、l左对齐，竖线表示2、3列间插入竖线 | + | \left[ \begin{array} {c c c c | c} |
| 1&a_{1,2}&\cdots&a_{1,n-1}&p(1)\\ | 1&a_{1,2}&\cdots&a_{1,n-1}&p(1)\\ | ||
| - | 1&a_{2,2}&\cdots&a_{2,n-1}&p(2)\\ | + | a_{2,1}&1&\cdots&a_{2,n-1}&p(2)\\ |
| \vdots&\vdots&\ddots&\vdots\\ | \vdots&\vdots&\ddots&\vdots\\ | ||
| a_{n-1,1}&a_{n-1,2}&\cdots&1&p(n-1)\\ | a_{n-1,1}&a_{n-1,2}&\cdots&1&p(n-1)\\ | ||
| 行 232: | 行 232: | ||
| 同理 $v\neq n$ 时也产生类似影响，因此单次处理复杂度 $O(6)$。 | 同理 $v\neq n$ 时也产生类似影响，因此单次处理复杂度 $O(6)$。 | ||
| - | 第二种操作对 $\text{dp}(u,t),E(u)$ 均产生影响，同样 $\text{dp}(u,t)$ 可以暴力计算，但 $E(u)$ 重新计算成分过高。 | + | 第二种操作对 $\text{dp}(u,t),E(u)$ 均产生影响，同样 $\text{dp}(u,t)$ 可以暴力计算，但 $E(u)$ 重新计算成本过高。 |
| 注意到 $E(u)$ 的增广矩阵仅有增广部分被修改，因此可以预处理出原矩阵的逆 $A^{-1}$，则有 | 注意到 $E(u)$ 的增广矩阵仅有增广部分被修改，因此可以预处理出原矩阵的逆 $A^{-1}$，则有 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest17.1630419429.txt.gz · 最后更改: 2021/08/31 22:17 由 jxm2001
