《P2151 [SDOI2009] HH 去散步》

题目描述

HH 有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时 HH 又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 1），问长度为 t，从给定地点 A 走到给定地点 B 共有多少条符合条件的路径。

输入格式

第一行：五个整数 N,M,t,A,B。其中 N 表示学校里的路口的个数，M 表示学校里的路的条数，t 表示 HH 想要散步的距离，A 表示散步的出发点，而 B 则表示散步的终点。

接下来 M 行，每行一组 Ai​,Bi​，表示从路口 Ai​ 到路口 Bi​ 有一条路。数据保证 Ai​=Bi​，但不保证任意两个路口之间至多只有一条路相连接。路口编号从 0 到 N−1。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模 45989。

输出格式

一行，表示答案。

输入输出样例

输入 #1复制

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

输出 #1复制

4

说明/提示

数据范围及约定

对于 30% 的数据，N≤4，M≤10，t≤10。

对于 100% 的数据，N≤50，M≤60，t≤230，0≤A,B。

代码实现：

#include<bits/stdc++.h> using namespace std ; const int mod = 45989 ; struct mat { int sz ; int m[ 222 ][ 222 ] ; void sqr() { mat res ; memset( res.m , 0 , sizeof( res.m ) ) , res.sz = sz ; for ( int i = 1 ; i <= sz ; i ++ ) for ( int j = 1 ; j <= sz ; j ++ ) for ( int k = 1 ; k <= sz ; k ++ ) res.m[ i ][ j ] = ( res.m[ i ][ j ] + ( m[ i ][ k ] * m[ k ][ j ] ) % mod ) % mod ; for ( int i = 1 ; i <= sz ; i ++ ) for ( int j = 1 ; j <= sz ; j ++ ) m[ i ][ j ] = res.m[ i ][ j ] ; } } trans , res ; int h[ 222 ] , t[ 222 ] , n , m , k , s , e , ans ; mat operator*( const mat &a , const mat &b ) { mat tmp ; memset( tmp.m , 0 , sizeof( tmp.m ) ) , tmp.sz = a.sz ; for ( int i = 1 ; i <= a.sz ; i ++ ) for ( int j = 1 ; j <= a.sz ; j ++ ) for ( int k = 1 ; k <= a.sz ; k ++ ) tmp.m[ i ][ j ] = ( tmp.m[ i ][ j ] + ( a.m[ i ][ k ] * b.m[ k ][ j ] ) % mod ) % mod ; return tmp ; } int main() { scanf( "%d%d%d%d%d" , &n , &m , &k , &s , &e ) , s ++ , e ++ ; for ( int i = 1 ; i <= m ; i ++ ) scanf( "%d%d" , &h[ i ] , &t[ i ] ) , h[ i + m ] = ++ t[ i ] , t[ i + m ] = ++ h[ i ] ; trans.sz = res.sz = m * 2 ; for ( int i = 1 ; i <= 2 * m ; i ++ ) for ( int j = 1 ; j <= 2 * m ; j ++ ) if ( ( j + m - i ) && ( i + m - j ) && ( t[ i ] == h[ j ] ) ) trans.m[ i ][ j ] = 1 ; for ( int i = 1 ; i <= 2 * m ; i ++ ) if ( h[ i ] == s ) res.m[ i ][ i ] = 1 ; k -- ; while ( k ) { if ( k % 2 ) res = res * trans ; k >>= 1 ; trans.sqr() ; } ans = 0 ; for ( int i = 1 ; i <= 2 * m ; i ++ ) if ( t[ i ] == e ) for ( int j = 1 ; j <= 2 * m ; j ++ ) ans = ( ans + res.m[ j ][ i ] ) % mod ; printf( "%d" , ans ) ; return 0 ; }