YZOJ P3527 [FJOI2018D1T3]城市路径问题

时间限制：1000MS      内存限制：131072KB

难度：\(6.5\)

• 题目描述

给出一张 \(n\) 个点的有向图 \(G(V, E)\) 。对于任意两个点 \(u, v\) （\(u\) 可以等于 \(v\) ），\(u\) 向 \(v\) 的连边数为：\(\sum\limits_{i=1}^k {out[u, i] \times in[v, i]}\) 。

给定 \(k\) 和数组 \(out, in\) ，现在有 \(m\) 个询问，每次询问给出三个参数 \(u, v, d\)，你需要回答从节点 \(u\) 出发，经过不超过 \(d\) 条边到达节点 \(v\) 的路径有多少种。

答案对 \(10^9+7\) 取模。

• 输入格式

第一行两个整数 \(n, k\) 。

接下来 \(n\) 行，第 \(i\) 行有 \(2k\) 个整数，前 \(k\) 个整数描述 \(out[i][]\)，后 \(k\) 个数描述 \(in[i][]\) 。

接下来一行一个整数 \(m\) 。

接下来 \(m\) 行，每行三个整数 \(u, v, d\)，描述一组询问。

• 输出格式

对于每个询问，输出一个方案数。由于答案可能太大，输出其除以 \(10^9+7\) 后的余数。

• 样例输入

• 样例输出

• 数据规模与约定

对于 \(40\%\) 的数据，\(n \leq 50 ,k \leq 20, m \leq 45\) 。

对于 \(90\%\) 的数据，\(n \leq 1000, k \leq 20, m \leq 50\) 。

对于另外 \(10\%\) 的数据，\(n \leq 1000, k=1, m \leq 100\) 。

所有输入数据不超过 int  范围。

 

 

 

Source: BZOJ 3583  （不是 FJOI 吗？www

---

 

 

 

首先，若矩阵 \(A\) 中 \((s, t)\) 的值表示从 \(s\) 到 \(t\) 的路径条数，那么 \(A^d\) 表示从 \(s\) 出发刚好经过 \(d\) 条路到达 \(t\) 的方案数。

可以考虑矩阵乘法的过程，\((i, j) = (i, k) \times (k, j)\) ，其实就是枚举经过点 \(k\) 把方案数乘起来，显然可以得到这个结论。

那么题目说的 “不超过 \(d\) 条” 的意思就是 \(A^0+A^1+A^2+ \cdots + A^d\) ，暴力算一下就会有 \(40pts\) 。

\(s \to t\) 的路径条数为 \(\sum\limits_{i=1}^k {out[s, i] \times in[t, i]}\) ，也可以看成是一个矩阵乘法的过程，即 \(OI^T\) 。

那么要求的是 \(G^d=\left(OI^T\right)^d\) ，若使用矩阵快速幂的话时间复杂度为 \(O(n^2k \log d)\)，因为计算一次 \(OI^T\) （\(O\) 为 \(n \times k\)，\(I^T\) 为 \(k \times n\)）需要 \(O(n^2k)\) 的复杂度，很明显无法通过本题（毕竟是 FJOI 的机子）。

考虑优化，根据矩阵乘法的结合律，有

\(G^d=\left(OI^T\right)^d = \underbrace{OI^T \times OI^T \times \cdots \times OI^T}_d \\ =O \times \underbrace{I^TO \times I^TO \times \cdots \times I^TO}_{d-1} \times I^T = O\left(I^TO\right)^{d-1}I^T\)

因为 \(I^T\) 为 \(k \times n\)，\(O\) 为 \(n \times k\)，所以计算一次 \(I^TO\) 的复杂度只是 \(O(nk^2)\)，而本题中 \(k\) 很小，可以接受。

另外，矩阵幂和没有什么 \(A^0+A^1+\cdots+A^d = \frac{A^{d+1}-1}{x-1}\) （不可能有好吧www），要想达到与快速幂同阶的复杂度，需要通过别的方法计算。

注意到

\(A^0+A^1+A^2+ \cdots A^{2n} = \left(A^0+A^1+\cdots+A^n\right) + A^n \left(A^0+A^1+\cdots+A^n\right)\)

\(A^0+A^1+A^2+ \cdots A^{2n+1} = \left(A^0+A^1+\cdots+A^n\right) + A^n \left(A^0+A^1+\cdots+A^n+A^{n+1}\right)\)

所以可以通过分治法在 \(O(\log d)\) 的复杂度内完成。

最后再对于每个询问的 \(s, t\) 乘一遍即可，时间复杂度 \(O\left(nk^2+mk^3\log d\right)\) 。