HDU 2157 How many ways?? 矩阵快速幂求A经过K个点到B方案数

本文主要是介绍HDU 2157 How many ways?? 矩阵快速幂求A经过K个点到B方案数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求A经过K个点到B方案数

1个0 1 的矩阵 A

a[i][j] = 1 表示i 到 j可达 或者说 i 到 j 有1条路 或者说i到j经过一个点的方案数 路可以重复走

 

而A2 = A* A

a[i][j] 的含义是

从i到j经过2个点的方案数

A的k次方 A[i,j]代表 i到j走k步的方案有a[i][j]

T组询问 x y z 快速幂求出A矩阵的y次 然后输出A[x][y]

#include <cstdio>
#include <cstring>
const int mod = 1000;
const int maxn = 22;
struct Mat
{int a[maxn][maxn];
};
Mat A, B, C, D;
int n, m;
Mat get(Mat x, Mat y)
{Mat z;memset(z.a, 0, sizeof(z.a));for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)for(int k = 1; k <= n; k++){z.a[i][j] += x.a[i][k]*y.a[k][j];z.a[i][j] %= mod;}return z;
}
void Mat_pow(int n)
{//puts("s");if(n <= 0)return;while(n){if(n&1)B = get(A, B);A = get(A, A);n >>= 1;}
}
int main()
{while(scanf("%d %d", &n, &m) && (n+m)){memset(D.a, 0, sizeof(D.a));memset(C.a, 0, sizeof(C.a));while(m--){int u, v;scanf("%d %d", &u, &v);u++;v++;D.a[u][v] = 1;}for(int i = 1;  i<= n; i++)C.a[i][i] = 1;int T;scanf("%d", &T);while(T--){int u, v, w;scanf("%d %d %d", &u, &v, &w);			u++;v++;B = C;A = D;Mat_pow(w);printf("%d\n", B.a[u][v]);}}return 0;
}

 

这篇关于HDU 2157 How many ways?? 矩阵快速幂求A经过K个点到B方案数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---