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