####Description 春天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅. 为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过k个地方, 比方说, 这次葱头决定经过2个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从A 点恰好经过k个点到达B点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上1000的余数就可以了. 你能帮帮他么?? 你可决定了葱头一天能看多少校花哦 ####Input 输入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点, 为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t < n) 表示从s点能到t点, 注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100), 接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0 当n, m都为0的时候输入结束 ####Output 计算每次询问的方案数, 由于走法很多, 输出其对1000取模的结果 ####Sample Input 4 4 0 1 0 2 1 3 2 3 2 0 3 2 0 3 3 3 6 0 1 1 0 0 2 2 0 1 2 2 1 2 1 2 1 0 1 3 0 0 ####Sample Output 2 0 1 3 ####Solution 设不同点之间的关系矩阵为M，M[i][j]=0表示i到j没有路，M[i][j]!=0表示i到j有路，根据给出的边构造出关系矩阵后，令A=M^k，则显然A[i][j]的值就是从i到j经过k个点的方法数，注意模的时候可能会出现负数 ####Code
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; const int maxn = 25; struct Mat { int mat[maxn][maxn]; //矩阵 int row, col; //矩阵行列数 }; Mat mod_mul(Mat a, Mat b, int p) //矩阵乘法 { Mat ans; ans.row = a.row; ans.col = b.col; memset(ans.mat, 0, sizeof(ans.mat)); for (int i = 0; i < ans.row; i++) for (int j = 0; j < ans.col; j++) for (int k = 0; k < a.col; k++) { ans.mat[i][j] += a.mat[i][k] * b.mat[k][j]; ans.mat[i][j] %= p; } return ans; } Mat mod_pow(Mat a, int k, int p) //矩阵快速幂 { Mat ans; ans.row = a.row; ans.col = a.col; for (int i = 0; i < a.row; i++) for (int j = 0; j < a.col; j++) ans.mat[i][j] = (i == j); while (k) { if (k & 1) ans = mod_mul(ans, a, p); a = mod_mul(a, a, p); k >>= 1; } return ans; } int n, m, mod = 1000; int main() { // freopen("in.txt", "r", stdin); while (~scanf("%d%d", &n, &m) && (m || n)) { Mat ans1; ans1.col = ans1.row = n; memset(ans1.mat, 0, sizeof(ans1.mat)); for (int i = 0; i < m; i++) { int s, t; scanf("%d%d", &s, &t); ans1.mat[s][t] = 1; } int T; scanf("%d", &T); for (int i = 0; i < T; i++) { int a, b, k; scanf("%d%d%d", &a, &b, &k); Mat ans2 = mod_pow(ans1, k, mod); printf("%d\n", (ans2.mat[a][b] % mod + mod) % mod); } } return 0; }