[题解]bzoj1875(SDOI2009)HH去散步

Description

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径

Input

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。 接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。

Output

一行，表示答案。

Sample Input

4 5 3 0 0 0 1 0 2 0 3 2 1 3 2

Sample Output

4

HINT

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。 对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Solution

这道题就是矩阵乘法，但是我们要把矩阵变一下。题目中要求不能立刻走回头路，但是又有重边，所以常规的邻接矩阵是不行的。我们要用边构矩阵。先把无向边拆成两条有向边，然后得出矩阵A，其中Ai,j=1$A_{i,j}=1$表示i号边可以到达j号边。然后求出At−1$A^{t-1}$，此时A′i,j$A'_{i,j}$就表示从i号边到j号边走了t-1条边的方案数。 然后我们枚举每条起点的出边i，对于每条出边再枚举每条终点的入边j，∑A′i,j$/sum A'_{i,j}$就是答案。

代码：