某島

… : "…アッカリ~ン . .. . " .. .
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