Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
弗洛伊德是一个大牛!给一个有向图G,他有n个结点,现在请你求出对于他的每一对结点(x,y),从x出发走恰好k条边以后恰好到达结点y的路径条数。
【输入格式】
输入文件第一行包含两个正整数n,k。(1<=n<=50,1<=k<=100)
接下来n行,每行n个用空格隔开的数。若第i行第j个数为1,则表示i到j在G中有一条边直接相连,若为0,则没有边直接相
连。
【输出格式】
输出文件包含n行,每行n个用空格隔开的数。表示从i出发走恰好k条边到达j的方案数。为了避免数字太大,请将所有数对8000取模。
Sample Input
2 1 0 1 1 0
Sample Output
0 1 1 0
【题解】
可以验证一下
3 2
0 1 0
0 0 1
0 0 0
->
0 0 1
0 0 0
0 0 0
表示只有一条路径从1到3是恰好走2格的。
答案就是改矩阵的K次方。
加一个快速幂就能过了。
和普通的乘法运算不同。
矩阵乘法的快速幂,退出条件为now<=1;而不是now=0;
因为now=1的时候没有必要再进行乘法运算了。因为一开始的初始状态就对于矩阵的1次方。
再乘会错解;
【代码】
#include <cstdio> const int MAXN = 51; const int MOD = 8000; int n, k,a[MAXN][MAXN],temp[MAXN][MAXN],temp1[MAXN][MAXN]; void input_data() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); temp[i][j] = a[i][j]; } } void solve(int now) { if (now == 1) return; solve(now >> 1); for (int i = 1;i <= n;i++)//每行乘每列! for (int what = 1; what <= n; what++)//这三个for可以自己推下。 { temp1[i][what] = 0; for (int j = 1; j <= n; j++) temp1[i][what] = (temp1[i][what] + temp[i][j] * temp[j][what]) % 8000; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) temp[i][j] = temp1[i][j]; if ((now %2)==1) { for (int i = 1; i <= n; i++) for (int what = 1; what <= n; what++) { temp1[i][what] = 0; for (int j = 1; j <= n; j++) temp1[i][what] = (temp1[i][what] + temp[i][j] * a[j][what]) % 8000; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) temp[i][j] = temp1[i][j]; } } void output_ans() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n - 1; j++) printf("%d ", temp[i][j]); printf("%d ", temp[i][n]); } } int main() { //freopen("F:\rush.txt", "r", stdin); //freopen("F:\rush_out.txt", "w", stdout); input_data(); solve(k); output_ans(); return 0; }