1 条题解
-
0
[R] Walk(dp_r)题解
题意简述
点简单有向图,求长度为 的有向路径数(所有有序点对,可重复经过边)。。
思路
矩阵视角
设 为邻接矩阵。则 = 从 到 恰好走 条边的路径数(乘法即"枚举中间点",加法即"路径拼接")。
答案:
快速幂
达 ,用二进制快速幂, 次矩阵乘法,每次 :
$$O(N^3 \log K) = 50^3 \times 60 \approx 7.5\times10^6.$$实现时可以只维护"答案矩阵",或用单位矩阵 作初值。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <vector> using namespace std; typedef vector<vector<long long>> Mat; const long long MOD = 1000000007LL; Mat mul(const Mat& A, const Mat& B) { int n = A.size(); Mat C(n, vector<long long>(n, 0)); for (int i = 0; i < n; i++) for (int k = 0; k < n; k++) { if (!A[i][k]) continue; long long aik = A[i][k]; for (int j = 0; j < n; j++) C[i][j] = (C[i][j] + aik * B[k][j]) % MOD; } return C; } int main() { int n; long long k; scanf("%d %lld", &n, &k); Mat A(n, vector<long long>(n)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%lld", &A[i][j]); Mat R(n, vector<long long>(n, 0)); for (int i = 0; i < n; i++) R[i][i] = 1; while (k) { if (k & 1) R = mul(R, A); A = mul(A, A); k >>= 1; } long long ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ans = (ans + R[i][j]) % MOD; printf("%lld\n", ans); return 0; }易错点
- 答案是所有有序点对的和,不是从某个固定点出发。
- 必须用
long long读( 超 int)。 - 矩阵乘法内层取模,并跳过 元素以提速。
- 保证无自环; 的情况按题面 ,但代码天然正确(单位阵的对角线和 )。
数据说明
共 21 组:5 组官方样例(含 );; 的小图(); 随机; 随机图的 ; 全 1 邻接(答案 之类大数)、全 0 邻接( 时答案 )。
- 1
信息
- ID
- 27
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者