题目链接：LibreOJ #6343. Sally Face 与地牢
做过 [Heoi 2014]林中路径 的同学应该対本题感到十分亲切，而在本题目，询问由平方和变为任意 \(r_i\) 次方和。
边无向和自环其实和边有向的情况完全相同，注意特判即可，关键问题为维护 \(r\) 次方和。
定义非负整数集合 \(S\) 用来存储路径长度，定义矩阵 $A_{[p]S}(0pr) $，表示从 \(i\) 点到 \(j\) 点，路径长度 \(k\in S\) 的路径长度的 \(p\) 次方和。
设 \(u\rightarrow k\) 有 \(a\) 条路径，长度为 \(c_1,c_2,\dots,c_{a}(c_i\in S_1)\) ， 设 \(k\rightarrow v\) 有 \(b\) 条路径，长度为 \(d_1,d_2,\dots,d_{b}(d_i\in S_2)\) ，我们有以下式子： \[ \begin{aligned} A_{[p]S_1\times S_2}[u][v] &= \sum_{i=1}^{a}\sum_{j=1}^{b}(c_i+d_j)^p\\ &=\sum_{i=1}^a\sum_{j=1}^b\sum_{t=0}^{p}\binom{p}{t}c_i^{p-t}d_j^{t}\\ &=\sum_{t=0}^{p}\binom{p}{t}\sum_{i=1}^a\sum_{j=1}^bA_{[p-t]S_1}[u][k]\cdot A_{[t]S_2}[k][v]\\ \end{aligned} \] 其中 $ S_1S_2 $ 表示一个集合 \(S'\)， 设\(S_1, S_2\) 进行笛卡尔积后为集合 \(\{(a_i,b_i)\}\)，则 $ S'={a_i+b_i} $。上面的形式符合矩阵乘法的运算法则，所以有： \[ A_{[p]S_1\times S_2}=\sum_{t=0}^p\binom{p}{t}A_{[p-t]S_1}\times A_{[t]S_2} \]
开始读入路径的长度都为 $ 1 $，直接读入 $ A_{[p]{1}}[i][j] $ ，运用刚才定义的矩阵运算计算，可得 $ A^i $ 为恰好走 \(i\) 步的答案，则 \(\sum_{i=1}^kA_{[p]}^i\) 即为最多走 $ k $ 步的答案 。对于 \(k\leq 10^{13}\) ，我们运用快速幂的思想加速计算，具体细节参考下面代码中的 \(\text{procedure()}\) 函数，时间复杂度为 \(O(n^3r^2logk+q)\) 。
注意到由于 \(r^2\) 的存在，这个复杂度无法通过此题，我们考虑在具体实现中把 $ i $ 次方和作为 $ (r+1)$ 元组放在一个矩阵中的每个位置，则每次做元组乘法时实际上是： \[ \begin{align} &(a_0,a_1,a_2,\dots,a_r)\\ &(b_0,\,b_1,\,b_2,\dots,b_r) \end{align} \] 其中下标表示路径长度的 $ i $ 次方和，则实际上上下两个式子做了一个卷积，且卷积每次相乘附带了一个二项式系数。设 \(c_i\) 为卷积后的第 $ i $ 次方和的答案，则： \[ \begin{align} c_i&=\sum_{j=0}^ia_j\cdot b_{i-j}\cdot \binom{i}{j}\\ &=\sum_{j=0}^ia_j\cdot b_{i-j}\cdot \frac{i!}{j!(i-j)!}\\ &=i!\sum_{j=0}^i\frac{a_j}{j!}\cdot \frac{b_{i-j}}{(i-j)!} \end{align} \] 用原数除下标的阶乘代替原数做快速傅立叶变换，之后乘以 \(i!\) 就是新的值，预处理阶乘及阶乘逆元即可。
至此问题解决，复杂度为 \(O(n^3r\text{log}r\cdot \text{log}k+q)\) 。
1 |
|
（\(n\) 年前某天在机房里出的题，结果std被同学们暴打，顶锅盖，逃……）