题解：CF1970E3 Trails (Hard)

· · 题解

看了眼题解区，好像还没有我这种思路的题解，决定写一份。不需要复杂的 dp 推导或矩阵推导的。

需要注意到：如果当前位于湖，再前往一个木屋，接下来就是直接从这个木屋回来了，这个过程的方案计算不受其它木屋的情况影响。

可将问题考虑为：一天的后半天从湖出发，选择一个木屋到达（如果这天的前半天走了短路，那么此时随便选一条路即可，否则只能选短路），第二天前半天再选择一条路走回来。

第一天前半天和最后一天后半天特殊考虑一下即可。

这个计算方法每次的转移都是一样的，可以用矩阵优化。并且状态只有两个（当天后半天必须走短路/长路短路都可以走）。

令 f_{i, 0 / 1} 表示第 i 天后半天长路短路都可以走/必须走短路，可得到转移方程：

dp_{i, 0} = dp_{i - 1, 0} \times \left(\sum\limits_{j = 1}^{m}s_{j}(s_{j} + l_{j})\right) + dp_{i - 1, 1} \times \left(\sum\limits_{j = 1}^{m}s_{j}^{2}\right)\\ dp_{i, 1} = dp_{i - 1, 0} \times \left(\sum\limits_{j = 1}^{m}l_{j}(s_{j} + l_{j})\right) + dp_{i - 1, 1} \times \left(\sum\limits_{j = 1}^{m}s_{j}l_{j}\right)

每次转移的系数都相同，可以提前处理一个转移矩阵然后快速幂优化。

显然 f_{1, 0} = s_{1}, f_{1, 1} = l_{1}，对于每个木屋计算一下其作为最后一天到达的木屋的方案数求和即为答案。

时间复杂度 \mathcal{O}(m + \log n)，其中 \log n 带了一个 2^{3} 的常数。

Code（省略 modint 以及 matrix 模板）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 1000000007;
matrix base, res;
int m, n, s[100005], l[100005];
modint ans, f0, f1;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> m >> n;
    for(int i = 1; i <= m; ++i) cin >> s[i];
    for(int i = 1; i <= m; ++i) cin >> l[i];
    for(int i = 1; i <= m; ++i) {
        base.val[0][0] += (s[i] + l[i]) * s[i], base.val[0][1] += (s[i] + l[i]) * l[i];
        base.val[1][0] += s[i] * s[i], base.val[1][1] += s[i] * l[i];
    }
    res = ksm(base, n - 1);//这里是快速幂优化
    f0 = s[1] * res.val[0][0] + l[1] * res.val[1][0];
    f1 = s[1] * res.val[0][1] + l[1] * res.val[1][1];
    for(int i = 1; i <= m; ++i) {
        ans += f0 * (s[i] + l[i]) + f1 * s[i];
    }
    cout << ans;
    return 0;
}