题目分析

Marisa 要从起点 $S$ 走到终点 $T$，每次走不同的路径，路径长度不超过 $K$，消耗体力为路径长度的平方。需要计算在所有不同路径上的体力消耗总和。

关键点：

• 统计所有长度 $\leq K$ 的不同路径
• 对每条长度为 $t$ 的路径，累加 $t^2$
• 答案对 $10^9+7$ 取模

解题思路

使用矩阵表示图的邻接关系，通过矩阵快速幂和分治策略高效计算：

1. 矩阵表示：邻接矩阵 $A$ 中 $A_{i,j}$ 表示从 $i$ 到 $j$ 的边数
2. 路径计数：$A^L$ 表示长度为 $L$ 的路径数量
3. 分治计算：使用分治法同时计算三个量：
   • $E0 = \sum_{i=1}^L A^i$（路径总数）
   • $E1 = \sum_{i=1}^L i \cdot A^i$（路径长度和）
   • $E2 = \sum_{i=1}^L i^2 \cdot A^i$（路径长度平方和）

关键公式

对于 $F(L) = \sum_{i=1}^L A^i$，有分治递推：

类似地，带权重的和式也有相应的递推关系。

完整代码

#include <bits/stdc++.h>
#define ci const int
#define ll long long
using namespace std;

ci N = 105, mod = 1e9 + 7;

inline int Mod(ci x) {
    return x < mod ? x : (x - mod);
}

int n, m, q;
ll k;

struct mat {
    int v[N][N];
    mat() {
        memset(v, 0, sizeof(v));
    }
    
    inline mat operator * (const mat &x) const {
        mat ans;
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    ans.v[i][j] = (ans.v[i][j] + (ll)v[i][k] * x.v[k][j]) % mod;
        return ans;
    }
    
    inline mat operator + (const mat &x) const {
        mat ans;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                ans.v[i][j] = Mod(v[i][j] + x.v[i][j]);
        return ans;
    }
    
    inline mat operator * (ci &x) const {
        mat ans;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                ans.v[i][j] = (ll)v[i][j] * x % mod;
        return ans;
    }
} A, Al, E0, E1, E2;

void Solve(ll L) {
    if (L == 1) {
        E0 = E1 = E2 = Al = A;
        return;
    }
    
    if (L & 1) {
        Solve(L - 1);
        Al = Al * A;
        mat e0 = E0, e1 = E1, e2 = E2;
        E0 = A + A * e0;
        E1 = A + A * (e1 + e0);
        E2 = A + A * (e2 + e1 * 2 + e0);
    } else {
        Solve(L >> 1);
        mat e0 = E0, e1 = E1, e2 = E2;
        ll half = L / 2;
        E0 = e0 + Al * e0;
        E1 = e1 + Al * (e1 + e0 * (half % mod));
        E2 = e2 + Al * (e2 + e1 * (L % mod) + e0 * ((__int128)half * half % mod));
        Al = Al * Al;
    }
}

int main() {
    scanf("%d%d%lld%d", &n, &m, &k, &q);
    
    for (int x, y; m; --m) {
        scanf("%d%d", &x, &y);
        ++A.v[x][y];
    }
    
    Solve(k);
    
    for (int x, y; q; --q) {
        scanf("%d%d", &x, &y);
        printf("%d\n", E2.v[x][y]);
    }
    
    return 0;
}

代码说明

• A：图的邻接矩阵，A.v[i][j] 表示从 $i$ 到 $j$ 的边数
• Al：$A^L$，长度为 $L$ 的路径数量矩阵
• E0：$\sum_{i=1}^L A^i$，长度 $\leq L$ 的路径总数
• E1：$\sum_{i=1}^L i \cdot A^i$，路径长度和
• E2：$\sum_{i=1}^L i^2 \cdot A^i$，路径长度平方和（最终答案）

Solve函数：

• 采用分治策略计算矩阵幂和相关和式
• 处理奇数情况和偶数情况的递推
• 使用 __int128 处理大数乘法

复杂度分析

• 时间复杂度：$O(N^3 \log K)$
  • 矩阵乘法：$O(N^3)$
  • 分治深度：$O(\log K)$
• 空间复杂度：$O(N^2)$