Nyoj 530 K steps[矩阵乘法求两点k步的方案数]

本文主要是介绍Nyoj 530 K steps[矩阵乘法求两点k步的方案数]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=530、

题目的意思很是简单，给你一个图，n个节点m条边。。（n最大100，m最大1000）。。。问走k步，有多少种方案。。最后mod 1991。。。（k最大为1000）。。

对于每个图。。。每次询问l次。。（l最大1000）。。

需要注意的是有重边。。。并且重边是不同的。。。。。。

学习了一下。。。Matrix67大牛的总结。。很是在理。。。。

经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
    把给定的图转为邻接矩阵，即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即可。

有点floyd的思想。。。。

有了这个知识背景，简直就是裸题。。。。。

Code：

 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;const int N = 105;
const int mod = 1991;
struct Matrix
{int n;int a[N][N];Matrix() {memset(a, 0, sizeof(a));// kidding me .}Matrix(int ax){n = ax;memset(a, 0, sizeof(a));}
} ans, A;Matrix operator * (Matrix a, Matrix b)
{Matrix tmpans;tmpans.n = a.n;for(int i = 1; i <= a.n; i ++){for(int j = 1; j <= a.n; j ++){for(int k = 1; k <= a.n; k ++)tmpans.a[i][j] = (tmpans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
//            printf("k = %d\n", tmpans.a[i][j]);}}return tmpans;
}void power(int k)
{while(k){if(k & 1) ans = ans * A;A = A * A;k = k >> 1;}
}int main()
{
//    freopen("1.txt", "r", stdin);int T;cin >> T;while(T --){int n, m, k, l;memset(A.a, 0, sizeof(A.a));memset(ans.a, 0, sizeof(ans.a));cin >> n >> m >> k >> l;A.n = n; ans.n = n;int x, y;for(int i = 1; i <= m; i ++){cin >> x >> y;A.a[x][y] = A.a[x][y] + 1;}for(int i = 1; i <= n; i ++){ans.a[i][i] = 1;}power(k);for(int i = 1; i <= l; i ++){cin >> x >> y;cout << ans.a[x][y] % mod << endl;}}return 0;
}

Matrix67大牛是总结还剩下最后一个。。。+u。。。明天就要看完了。。。

这篇关于Nyoj 530 K steps[矩阵乘法求两点k步的方案数]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---