描述
在某個神秘的星球上有一個游樂園
游樂園里有一個奇怪的迷宮，迷宮內有n個點，每個點之間都可能會有一條有向邊（可能會有自環）
現在游樂園主有個問題想請你幫忙：
問：從s點走到f點，恰好走過m條邊（邊可以重復走），總共有多種不同的方案（兩種方案只要有一條邊不同，就是不同方案）
現在你只需要輸出方案數對P取模的結果就可以了

格式
輸入格式
一個整數n
下面跟著n行n列的鄰接矩陣，兩個數之間有一個空格
在下一行依次是整數m,s,f,p

1<=n,s,f<=50
1<=m<=10^6
1<=p<=10^5

輸出格式
一個數即方案數對P取模的結果

樣例1
樣例輸入1
5
0 1 1 1 1
0 0 0 0 0
1 1 0 1 1
0 0 0 0 1
0 0 0 0 1
3 1 5 1994
樣例輸出1
5
限制
各個測試點1s

思路分析：披著dp外衣的矩陣乘法。據說大犇都能一眼看出這是矩陣乘法，反正我是看不出來，看了代碼恍然大悟，當然一般人看不出來無非就是做題少，見得多了思路自然就清晰了。如果兩點可達，那么我們定義為d[i][j] = 1，反之d[i][j] = 0。假設矩陣d為矩陣x的平方，那么d[i][j] = x[i][k] * x[k][j]就表示i到j經過了2條邊的方案數。如果是k條邊，則對x進行k次平方就可以了。

import java.util.Scanner;public class Main {static int n;static int m, s, f, p;static int[][] d, ans;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();d = new int[n + 1][n + 1];ans = new int[n + 1][n + 1];for (int i = 1; i <= n; i++) {ans[i][i] = 1;for (int j = 1; j <= n; j++) {d[i][j] = in.nextInt();}}m = in.nextInt();s = in.nextInt();f = in.nextInt();p = in.nextInt();while (m > 0) {if (m % 2 == 1) {ans = chengfa(d, ans);}d = chengfa(d, d);m >>= 1;}System.out.println(ans[s][f] % p);}private static int[][] chengfa(int[][] a, int[][] b) {// TODO Auto-generated method stubint[][] c = new int[n + 1][n + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {c[i][j] += a[i][k] * b[k][j];c[i][j] %= p;}}}return c;} }

總結

以上是生活随笔為你收集整理的Vijos 1603 ----迷宫（矩阵乘法，矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

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