DDOSvoid's Blog

bzoj 3583 杰杰的女性朋友

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

简要题意：给定一个 $n\times m$ 的矩阵 $X$ 和一个 $m\times n$ 的矩阵 $Y$，现在有 $q$ 次询问，每次询问给定 $u,v,d$，求 $\sum_{i=0}^d(XY)^i_{u,v}$

$n\le 1000,m\le 20, q\le 50$

Solution

我们注意到 $XY$ 是一个 $n\times n$ 的矩阵，而 $YX$ 是一个 $m\times m$ 的矩阵，所以我们将 $(XY)^k$ 拆成 $X(YX)^{k-1}Y$，对于 $\sum_{i=0}^{d-1}(YX)^i_{u,v}$ 可以 $O(m^3\log d)$ 求，那么总复杂度就是 $O(qm^3\log d)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#define maxn 1010
#define maxm 21
#define ll long long
using namespace std;

const int p = 1000000007;
const ll pq = 1ll * p * p; 
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; } 

struct Matrix {
    static const int n = 20; 
    int a[n + 1][n + 1];
    
    Matrix() { clear(); }
    inline void setone() { clear(); for (int i = 1; i <= n; ++i) a[i][i] = 1; }
	inline void clear() { fill(a[0], a[0] + (n + 1) * (n + 1), 0); }
    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix w;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                ll res = 0;
                for (int k = 1; k <= n; ++k) {
                    res += 1ll * u.a[i][k] * v.a[k][j];
                    if (res >= pq) res -= pq;
                } w.a[i][j] = res % p;
            }
        return w;
    }
    friend Matrix operator + (const Matrix &u, const Matrix &v) {
        Matrix w;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) w.a[i][j] = add(u.a[i][j], v.a[i][j]);
        return w; 
    }
} I;
Matrix pow(Matrix x, int n) {
    Matrix s; s.setone();
    for (; n; n >>= 1, x = x * x)
        if (n & 1) s = s * x;
    return s; 
}
Matrix calc(Matrix x, int n) {
    if (n == 0) return I;
    if (n & 1) return calc(x, n / 2) * (I + pow(x, n / 2 + 1));
    else {
        Matrix tmp = pow(x, n / 2); 
        return calc(x, n / 2 - 1) * (I + tmp * x) + tmp;
    }
}

int n, m, q; 

int f[maxn][maxm], g[maxm][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) { 
        for (int j = 1; j <= m; ++j) cin >> f[i][j];
        for (int j = 1; j <= m; ++j) cin >> g[j][i];
    }
    Matrix sx; I.setone();
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= m; ++j) sx.a[i][j] = add(sx.a[i][j], mul(g[i][k], f[k][j]));
    cin >> q; 
    while (q--) { 
        int x, y, z; cin >> x >> y >> z;
        if (!z) { cout << (x == y) << "\n"; continue; }
        Matrix s = calc(sx, z - 1); int ans = x == y;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= m; ++j) ans = add(ans, mul({ f[x][i], s.a[i][j], g[j][y] }));
        cout << ans << "\n";
    }
    return 0;
}