Brief description :
给定一个可能重边但没有自环的无向图，要求计算 A, B 两点之间步数为 t 的方案数。答案模 45989。
（可以经过某个点某条边多次，但是不可以立即沿着同一条边折返。）
（.. N <= 20, M <= 60, t <= 2^30 ..）
Analyse :
由于“不会沿着同一条边折返”，因此从 A 点经过 k 步後的状态仅与最后一步所走的边和它的方向有关。
如果将每条无向边拆成两条有向边，那么仅于边有关。
F[i][j] : 已经走了 i 步，最后一步走过的边是 i 的方案数。
#include
using namespace std;
const int N = 20, M = 60, MM = 2 * M;
const int _P = 45989;
struct Edge{
int x, y;
} E[MM];
int n, m, t, a, b;
int ans, mm, x, y;
struct matrix{
int d[MM][MM];
matrix(){
memset(d, 0, sizeof(d));
}
} A, C;
matrix operator *(const matrix& a, const matrix& b){
matrix c;
for (int i=0;i
External link :
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1875
