#P4362. Graph

    ID: 3565 传统题 1000ms 512MiB 尝试: 26 已通过: 20 难度: 7 上传者: 标签>CF2200提高+/省选-矩阵快速幂等比数列求和低秩矩阵幂降维

Graph

题目描述

给定一张 nn 个点的有向图 G=(V,E)G=(V,E)。

对于任意两个点 u,v(1≤u,v≤n)u,v(1\le u,v\le n),uu 向 vv 的连边数为:$\sum_{i=1}^k \operatorname{out}(u,i)\times \operatorname{in}(v,i)$。

现在给出 mm 个询问,每次询问给出三个参数 u,v,du,v,d,你需要回答从节点 uu 出发,经过不超过 dd 条边到达节点 vv 的路径有多少种。答案对 109+710^9+7 取模。

输入格式

第一行两个整数 n,kn,k。

接下来 nn 行,对于第 (i+1)(i+1) 行 2k2k 个整数,前 kk 个整数表示 out⁡(i,j)\operatorname{out}(i,j),后 kk 个数描述 in⁡(i,j)\operatorname{in}(i,j)。

第 n+2n+2 行一行一个整数 mm 表示询问次数。

接下来 mm 行,每行三个整数 u,v,d(0≤d<231)u,v,d(0 \le d \lt 2^31),描述一组询问。

输出格式

对于每个询问,输出一行一个整数,描述答案。

5 2
2 5 4 3
7 9 2 4
0 1 5 2
6 3 9 2
2147483647 1000000001 233522788488
10
1 1 0
2 2 1
2 4 5
4 3 10
3 4 50
1 5 1000
1
51
170107227
271772358
34562176
890241289

提示

对于 100%100\% 的数据,1≤n≤10001\le n\le 1000,\1lek≤20\1le k\le 20,1≤m≤501\le m\le 50。

题目来源

没有写明来源