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\)，描述一组询问。
-
输出格式