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
                                                												

													Posted by 
													xiaodao													
													Category: 													日常