BZPRO

#3610. [Heoi2014]林中路径

内存限制：256 MiB 时间限制：50 Sec
提交 提交记录 讨论

题目描述

Alice 和 Marisa 都住在一个巨大的由 N 个路口与 M 条单向小道构成的森林中。Marisa 非常喜
欢到 Alice 家里去玩，但是 Alice 并不喜欢这位鲁莽的来客。Alice 非常擅长观察， 因此每当她发
现 Marisa 走了一条与之前完全相同的路径来到她家时，她就会装作不在家， Marisa 就只好败兴而
归。Marisa 发现了这个秘密，因此她决定每次走不同的路径到 Alice 家。
   Marisa 体力有限，她不想走超过 K 条边到达 Alice 家，并且，每当她走 t（t≤K）条边 到达 
Alice 家时，她需要付出 t2的体力。Marisa 想知道，在 Alice 无论如何都不想接见她 之前（即 
Marisa 无法走一条长度不超过 K 的与之前不同的路径），她会消耗多少体力。
   现在 Marisa 拿到了一张森林的地图，但因为 Marisa 非常笨，她并不知道自己的家和 Alice 的
家在哪一个路口，因此她会给询问你 Q 次，每次询问假如 Marisa 的家的位置在 S 而 Alice 的家
的位置在 T 时的答案。
    一条路径 A 的定义是指一个长度为 P（P 可以为任意正整数或零）的边的序列 Am0,Am1,Am2,…
,AmT-1，其中对于任意 1≤i＜P，有 Ami-1的结束节点是 Ami的起始节点。 
   两条路径 A 和 B 完全相同是指两条路径的长度均为 T 并且对任意 0≤i＜P，有 Ami=Bmi。

输入格式

输入数据第一行包含四个整数 N,M,K,Q，含义如题所述。 

 接下来 M 行，每行两个整数 X,Y，表示从第 X 个路口到第 Y 个路口有一条单向小道。
路 口的标号为 1,2,3,…,N，在输入数据第 i+1 行的边的标号为 i。 
 接下来 Q 行，每行两个整数 S 和 T，含义如题所述。 

输出格式

对于每个询问，输出一行，表示这次询问的答案。由于 Marisa 接受不了非常大的数， 你只需
要输出答案模 1,000,000,007 的值。 

样例

样例输入


			
#1

2 0 1 1

1 2



#2

2 2 2 1

1 2

2 1

1 1



#3

2 2 100 1

1 2

2 1

1 2





#4

2 3 100 2

1 2

1 2

2 1

2 2

2 1

样例输出


			
#1

0



#2

4



#3

166650



#4

632506153

518794755

数据范围与提示

 对于 100%的数据，2≤N≤100，0≤M≤100,000，0≤K≤1,000,000,000，0≤Q≤10,000， 1≤X，Y，S，T≤N


样例一解释 从 S 到 T 不存在路径  

样例二解释 Marisa 可以重复经过一个路口，即使这个路口就是 Alice 的家或 Marisa 的家 

BZPRO Powered by Remmina.
Github Repository