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)$ 。