Editorial for Atcoder Educational DP Contest R - Walk
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta nhận được đồ thị ~G~ được biểu diễn dưới dạng ma trận kề ~a~ và ta muốn tính số đường đi có độ dài ~K~. Đầu tiên, ta chuyển ~a~ sang ma trận ~m~.
Nhận thấy rằng khi ta nhân ~m~ với ~m~, ta nhận được số lượng đường đi với độ dài ~2~ giữa từng cặp đỉnh ~i, j~. Vậy nếu với ma trận ~m^p~, ta sẽ có số đường đi độ dài ~p~ với từng cặp đỉnh ~i, j~.
Như vậy, thứ chúng ta đang tìm là ~m^K~ và có thể được tính bằng cách nhân ma trận và dùng kĩ thuật chia để trị để tính lũy thừa nhanh.
Độ phức tạp: ~\mathcal{O}(N^3\log{}K)~
Code mẫu
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; int add(int i, int j) { i += j; if (i >= MOD) i -= MOD; return i; } int mul(int i, int j) { return int((long long) i * j % MOD); } struct Matrix{ int m[50][50]; }; Matrix MatrixMultiplication(Matrix a, Matrix b) { Matrix res; memset(res.m, 0, sizeof(res.m)); for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { for (int k = 0; k < 50; k++) { res.m[i][j] = add(res.m[i][j], mul(a.m[i][k], b.m[k][j])); } } } return res; } Matrix MatrixPower(Matrix a, long long k) { Matrix res; memset(res.m, 0, sizeof(res.m)); for (int i = 0; i < 50; i++) res.m[i][i] = 1; while (k > 0) { if (k & 1) res = MatrixMultiplication(res, a); a = MatrixMultiplication(a, a); k >>= 1; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n; long long k; cin >> n >> k; Matrix a; memset(a.m, 0, sizeof(a.m)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a.m[i][j]; } } a = MatrixPower(a, k); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans = add(ans, a.m[i][j]); } } cout << ans; }
Comments