某岛

… : "…アッカリ~ン . .. . " .. .
March 24, 2011

[SDOI 2009] HH去散步

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