HDOJ How many ways?? 2157【矩阵高速幂】

How many ways?

?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2046    Accepted Submission(s): 758

Problem 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

 

Author

小黑

 

Source

2008信息project学院集训队——选拔赛

 

Recommend

linle   |   We have carefully selected several similar problems for you:  2159 2154 2158 2156 2153 

 

中文题~

解题思路：经典矩阵算法。把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，假设要求经过k步的路径数，我们仅仅须要二分求出A^k就可以。

第一道矩阵高速幂。写的比較乱。并且这样的写法时间复杂度较高，没有优化。只是比較easy看懂。

矩阵高速幂预备知识：

       ①矩阵相乘规则：

       矩阵与矩阵相乘 第一个矩阵的列数必须等于第二个矩阵的行数 假如第一个是m*n的矩阵 第二个是n*p的矩阵 则结果就是m*p的矩阵 且得出来的矩阵中元素具有下面特点：
第一行第一列元素为第一个矩阵的第一行的每一个元素和第二个矩阵的第一列的每一个元素乘积的和 以此类推 第i行第j列的元素就是第一个矩阵的第i行的每一个元素与第二个矩阵第j列的每一个元素的乘积的和。

②单位矩阵：

       n*n的矩阵  mat ( i , i )=1;  不论什么一个矩阵乘以单位矩阵就是它本身 n*单位矩阵=n， 能够把单位矩阵等价为整数1.

  ③高速幂：

这里矩阵高速幂等价于整数的高速幂，这里不再具体讲述

上代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>


int s[25][25];
int b[25][25];
int n,m;
int a[25][25];

void Mat(int x[25][25],int y[25][25],int modn)
{
	int c[25][25];
	memset(c,0,sizeof(c)); //记得初始化 
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				c[i][j]=(c[i][j]+x[i][k]*y[k][j]%modn)%modn;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		x[i][j]=c[i][j];
}

int Matrix(int begin,int end,int k)
{	
	for(int i=0;i<n;i++){ //初始化一个单位矩阵 
		for(int j=0;j<n;j++){
			a[i][j]=(i==j);
		}
	}
	for(int i=0;i<n;i++){  //记得用s保存再赋给b，不然b值变了之后结果就不正确了 
		for(int j=0;j<n;j++){
			b[i][j]=s[i][j];
		}
	}
	while(k){
		if(k&1)Mat(a,b,1000);
		Mat(b,b,1000);
		k>>=1;
	}
	return a[begin][end];
}

int main()
{
	while(scanf("%d%d",&n,&m),n!=0||m!=0){
		int S,G;
		memset(b,0,sizeof(b));
		memset(s,0,sizeof(s));
		for(int i=0;i<m;i++){
			scanf("%d%d",&S,&G);
			s[S][G]=1;
		}
		int T;
		scanf("%d",&T);
		int B,E,k;
		while(T--){
			scanf("%d%d%d",&B,&E,&k);
			int res=Matrix(B,E,k);
			printf("%d
",res);
		}
	}
	return 0;
}