核心内容摘要
穿越边界的灵感风暴：全维度探索欧美精彩内容的无限可能
题目描述HH 有个一成不变的习惯喜欢饭后百步走。
所谓百步走就是散步就是在一定的时间内走过一定的距离。
但是同时 HH 又是个喜欢变化的人所以他不会立刻沿着刚刚走来的路走回。
又因为 HH 是个喜欢变化的人所以他每天走过的路径都不完全一样他想知道他究竟有多少种散步的方法。
现在给你学校的地图假设每条路的长度都是一样的都是 1问长度为 t从给定地点 A 走到给定地点 B 共有多少条符合条件的路径。
输入格式第一行五个整数 N,M,t,A,B。
其中 N 表示学校里的路口的个数M 表示学校里的路的条数t 表示 HH 想要散步的距离A 表示散步的出发点而 B 则表示散步的终点。
接下来 M 行每行一组 Ai,Bi表示从路口 Ai 到路口 Bi 有一条路。
数据保证 AiBi但不保证任意两个路口之间至多只有一条路相连接。
路口编号从 0 到 N−1。
同一行内所有数据均由一个空格隔开行首行尾没有多余空格。
没有多余空行。
答案模 45989。
输出格式一行表示答案。
输入输出样例输入 #1复制4 5 3 0 0 0 1 0 2 0 3 2 1 3 2输出 #1复制4说明/提示数据范围及约定对于 30% 的数据N≤4M≤10t≤10。
对于 100% 的数据N≤50M≤60t≤2300≤A,B。
代码实现#includebits/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 ; }