1 条题解

  • 0
    @ 2026-11-12 21:58:04

    [R] Walk(dp_r)题解

    题意简述

    NN 点简单有向图,求长度为 KK 的有向路径数(所有有序点对,可重复经过边) mod 109+7\bmod 10^9+7。K≤1018K \le 10^{18}。

    思路

    矩阵视角

    设 AA 为邻接矩阵。则 (AK)i,j(A^K)_{i,j} = 从 ii 到 jj 恰好走 KK 条边的路径数(乘法即"枚举中间点",加法即"路径拼接")。

    答案:

    ∑i=1N∑j=1N(AK)i,j.\sum_{i=1}^{N}\sum_{j=1}^{N} (A^K)_{i,j}.

    快速幂

    KK 达 101810^{18},用二进制快速幂,O(log⁡K)O(\log K) 次矩阵乘法,每次 O(N3)O(N^3):

    $$O(N^3 \log K) = 50^3 \times 60 \approx 7.5\times10^6.$$

    实现时可以只维护"答案矩阵",或用单位矩阵 II 作初值。

    复杂度

    时间 O(N3log⁡K)O(N^3\log K),空间 O(N2)O(N^2)。

    参考代码

    #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;
    }
    

    易错点

    1. 答案是所有有序点对的和,不是从某个固定点出发。
    2. KK 必须用 long long 读(101810^{18} 超 int)。
    3. 矩阵乘法内层取模,并跳过 00 元素以提速。
    4. ai,i=0a_{i,i}=0 保证无自环;K=0K=0 的情况按题面 K≥1K\ge1,但代码天然正确(单位阵的对角线和 =N=N)。

    数据说明

    共 21 组:5 组官方样例(含 K=1018K=10^{18});N=1N=1;N=2/3N=2/3 的小图(K=1,2,3K=1,2,3);N=5/10N=5/10 随机;N=50N=50 随机图的 K=1,103,106,1018K=1,10^3,10^6,10^{18};N=50N=50 全 1 邻接(答案 (N−1)K⋅N(N-1)^K \cdot N 之类大数)、全 0 邻接(K≥1K\ge1 时答案 00)。

    • 1

    信息

    ID
    27
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    1
    已通过
    1
    上传者