YZOJ P3527 [FJOI2018D1T3]城市路径问题

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

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注