2011-06-13 22:23:43Morris
d769. 共有多少種走法?
http://zerojudge.tw/ShowProblem?problemid=d769
內容 ：
-------不想廢話了--------
給定一個有N個點的單向無權圖(編號1~N)，請問從點i走k步後到點j共有多少種走法呢?
給定一個有N個點的單向無權圖(編號1~N)，請問從點i走k步後到點j共有多少種走法呢?
輸入說明
：
每組測資的第一行給定節點數N及步數k
接下來好多行敘述此單向圖，
每一行的x y s代表從點x直達點y共有s條路徑，而每條路徑都是一步到達
以0 0 0代表此圖敘述結束
例如第一組範例測資:
3 3
1 2 2
2 1 1
2 3 4
2 2 1
3 1 2
0 0 0
代表從點1到點2共有2條路徑直達
注意2 2 1代表點2到點2有1條路徑，是合法輸入
若有未敘述到的代表那兩點間直達路徑數是0
測資保證不會有重覆輸入或不合法的節點編號出現
然後輸入詢問數Q，代表有Q行詢問
接下來Q行各有兩個數i j，請對每一組i j 輸出從i出發，走k步剛好到達j共有多少種走法
另外因為答案可能好大，所以請輸出 mod 5281的答案
注意途中可以先經過j沒關係，只要第k步能剛好到達j就行了
走過的路徑都可以再走。
範圍: 1<=N<=50，Q<=N2，0<=s<=20，1<=k<=10000000
接下來好多行敘述此單向圖，
每一行的x y s代表從點x直達點y共有s條路徑，而每條路徑都是一步到達
以0 0 0代表此圖敘述結束
例如第一組範例測資:
3 3
1 2 2
2 1 1
2 3 4
2 2 1
3 1 2
0 0 0
代表從點1到點2共有2條路徑直達
注意2 2 1代表點2到點2有1條路徑，是合法輸入
若有未敘述到的代表那兩點間直達路徑數是0
測資保證不會有重覆輸入或不合法的節點編號出現
然後輸入詢問數Q，代表有Q行詢問
接下來Q行各有兩個數i j，請對每一組i j 輸出從i出發，走k步剛好到達j共有多少種走法
另外因為答案可能好大，所以請輸出 mod 5281的答案
注意途中可以先經過j沒關係，只要第k步能剛好到達j就行了
走過的路徑都可以再走。
範圍: 1<=N<=50，Q<=N2，0<=s<=20，1<=k<=10000000
輸出說明
：
對每一個詢問i j
輸出從i出發，走k步剛好到達j共有多少種走法 mod 5281的答案
輸出從i出發，走k步剛好到達j共有多少種走法 mod 5281的答案
範例輸入 ：
3 3 1 2 2 2 1 1 2 3 4 2 2 1 3 1 2 0 0 0 9 1 2 1 1 2 1 1 3 2 2 2 3 3 1 3 2 3 3 2 4 1 1 1 1 2 3 2 1 5 0 0 0 3 1 1 1 2 2 1
範例輸出 ：
6 18 11 8 21 12 4 4 16 271 93 155
提示
：
O(N3logk)
出處
：
/**********************************************************************************/
/* Problem: d769 "共有多少種走法?" from 國文課時的靈機一動(誤 */
/* Language: C */
/* Result: AC (412ms, 364KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 08:21:20 */
/**********************************************************************************/
#include<stdio.h>
typedef struct {
int t[50][50];
}Matrix;
Matrix A, In, init;
Matrix mult(Matrix x, Matrix y, int n) {
Matrix t = init;
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++) {
t.t[i][k] += x.t[i][j]*y.t[j][k];
}
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
t.t[i][j] %= 5281;
return t;
}
int ans(int k, int n) {
Matrix x = In, y = A;
while(k) {
if(k&1) x = mult(x, y, n);
y = mult(y, y, n);
k /= 2;
}
int Q, i, j;
scanf("%d", &Q);
while(Q--) {
scanf("%d %d", &i, &j);
printf("%d\n", x.t[i-1][j-1]);
}
}
main() {
int n, a, b, k, x, y, s;
while(scanf("%d %d", &n, &k) == 2) {
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
A.t[a][b] = 0, In.t[a][b] = 0,
init.t[a][b] = 0;
for(a = 0; a < n; a++) In.t[a][a] = 1;
while(scanf("%d %d %d", &x, &y, &s) == 3) {
if(x + y + s == 0) break;
A.t[x-1][y-1] += s;
}
ans(k, n);
}
return 0;
}
上一篇：a054. 電話客服中心
下一篇：a068. E. 看動畫 加强版