描述

無向圖邊長均為1, 求從給定地點A走到給定地點B共有多少條長度為 t 的路徑(不能連續走重復的邊). 模45989.

分析

• f[i][k] : 當走到邊 i 的終點的時候路徑長度為 j 的方案數量
• f[i][k] : 可以由 f[j][k-1] 轉移來的條件是邊 j 的終點是i的起點
• 那么就可以構造矩陣來解了...
• 不用矩陣是不是也能解？

代碼
#include #include #include using namespace std; typedef long long lli;const int maxn = 120 + 10; const int mod = 45989;struct Edge {int u, v; };vectoredges;struct Matrix {int n, m;int a[maxn][maxn];Matrix(int n=0, int m=0) : n(n), m(m) { memset(a, 0, sizeof(a)); }Matrix operator ^ (int p) {Matrix t = Matrix(n, n), A = *this;for(int i = 0; i < n; i++) t.a[i][i] = 1;for(; p; p>>=1, A=A*A) if(p & 1) t = t*A;return t;}Matrix operator * (Matrix A) {Matrix ret = Matrix(n, A.m);for(int i = 0; i < n; i++)for(int j = 0; j < A.m; j++) {ret.a[i][j] = 0;for(int k = 0; k < m; k++)ret.a[i][j] = ((lli)a[i][k]*A.a[k][j] + ret.a[i][j]) % mod;}return ret;}void print() {for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++)printf("%d ", a[i][j]);printf("\n");}} };void AddEdge(int u, int v) {edges.push_back((Edge){u, v});edges.push_back((Edge){v, u}); }int main() {int n, m, t, a, b;scanf("%d %d %d %d %d", &n, &m, &t, &a, &b);a--; b--; t--;for(int i = 0; i < m; i++) {int u, v;scanf("%d %d", &u, &v);u--; v--;AddEdge(u, v);}m += m;Matrix F = Matrix(1, m), A = Matrix(m, m);for(int i = 0; i < m; i++) {Edge& e = edges[i];if(e.u == a) F.a[0][i] = 1;for(int j = 0; j < m; j++) {Edge& e2 = edges[j];if(e.v == e2.u && i != (j^1)) A.a[i][j] = 1;}}F = F * (A^t);int ans = 0;for(int i = 0; i < m; i++) {Edge& e = edges[i];if(e.v == b) ans = (ans + F.a[0][i]) % mod;}printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-1875-HH去散步-SDOI2009-矩阵乘法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。