P2151 [SDOI2009]HH去散步

題意：

HH有個一成不變的習慣，喜歡飯后百步走。所謂百步走，就是散步，就是在一定的時間 內，走過一定的距離。 但是同時HH又是個喜歡變化的人，所以他不會立刻沿著剛剛走來的路走回。 又因為HH是個喜歡變化的人，所以他每天走過的路徑都不完全一樣，他想知道他究竟有多 少種散步的方法。

現在給你學校的地圖（假設每條路的長度都是一樣的都是1），問長度為t，從給定地 點A走到給定地點B共有多少條符合條件的路徑

題解：

這題跟裸的矩陣快速冪唯一區別是，本題中不允許剛經過的邊，本題中給的是無向邊，頓時沒有什么思路。
我們可以點邊互換，將邊成是點，然后再重新建邊，如果原圖中有4個邊，分別編號1~4，然后我們依次判斷第i個邊的尾和第j個邊的頭是否連接，如果連接就從第i個邊向第j個邊連一條邊，
如何處理走回去的情況，只要我們同一條邊拆出來的兩個點互不連邊即可

代碼：

// Problem: P2151 [SDOI2009]HH去散步 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P2151 // Memory Limit: 125 MB // Time Limit: 1000 ms // Data:2021-08-13 16:47:00 // By Jozky #include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; template <typename T> inline void read(T& x) {T f= 1;x= 0;char ch= getchar();while (0 == isdigit(ch)) {if (ch == '-')f= -1;ch= getchar();}while (0 != isdigit(ch))x= (x << 1) + (x << 3) + ch - '0', ch= getchar();x*= f; } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); }const int maxn= 151, mod= 45989; int n, m, s, t, x[maxn], y[maxn], cnt; ll T; struct Ma {ll m[maxn][maxn]; }; Ma mul(Ma a, Ma b, int n) {Ma temp;memset(&temp, 0, sizeof(temp));for (int i= 1; i <= n; i++) {for (int j= 1; j <= n; j++) {for (int k= 1; k <= n; k++) {temp.m[i][j]= (temp.m[i][j] + ((a.m[i][k] % mod) * (b.m[k][j]) % mod) % mod) % mod;}}}return temp; } Ma poww(Ma res, ll N, int n) {Ma ans;for (int i= 1; i <= n; i++) {ans.m[i][i]= 1;}while (N) {if (N & 1)ans= mul(ans, res, n);res= mul(res, res, n);N>>= 1;}return ans; } Ma A; void add(int u, int v) {x[++cnt]= u;y[cnt]= v; } int main() {//rd_test();scanf("%d%d%lld%d%d", &n, &m, &T, &s, &t);s++;t++;x[++cnt]= 0;y[cnt]= s;for (int i= 1, u, v; i <= m; i++) {scanf("%d%d", &u, &v);u++, v++;x[++cnt]= u, y[cnt]= v;x[++cnt]= v, y[cnt]= u;}for (int i= 1; i <= cnt; i++)for (int j= 1; j <= cnt; j++)if (i != j && i != (j ^ 1)) {if (y[i] == x[j])A.m[i][j]= 1;}Ma Ans= poww(A, T, cnt);int ans= 0;for (int i= 1; i <= cnt; i++)if (y[i] == t) {ans= (ans + Ans.m[1][i]) % mod;}cout << ans << endl;return 0;//Time_test(); }

總結

以上是生活随笔為你收集整理的P2151 [SDOI2009]HH去散步的全部內容，希望文章能夠幫你解決所遇到的問題。

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