官方题解｜巨大的表格

题目解析

我们可以先计算出 $1$ 列的所有元素的值，然后考虑表格中每一列元素的值，可以发现，对于 $i(i > 1)$ 列的 $N$ 个元素的值，可以完全由 $i - 1$ 列的元素得到：

$$\begin{split} A_{0, i} = A_{0, i - 1} + 1 \end{split}$$

$$\begin{split} A_{1, i} &= A_{0, i} \times S + A_{1, i - 1} \times T \\ &= (A_{0, i - 1} + 1) \times S + A_{1, i - 1} \times T \\ &= A_{0, i - 1} \times S + A_{1, i - 1} \times T + S \end{split}$$

$$\begin{split} A_{2, i} &= A_{1, i} \times S + A_{2, i - 1} \times T \\ &= (A_{0, i - 1} \times S + A_{1, i - 1} \times T + S) \times S + A_{2, i - 1} \times T\\ &= A_{0, i - 1} \times S^2 + A_{1, i - 1} \times ST + A_{2, i - 1} \times T + S^2 \end{split}$$

$$\begin{split} A_{3, i} &= A_{2, i} \times S + A_{3, i - 1} \times T \\ &= (A_{0, i - 1} \times S^2 + A_{1, i - 1} \times ST + A_{2, i - 1} \times T + S^2) \times S + A_{3, i - 1} \times T\\ &= A_{0, i - 1} \times S^3 \times A_{1, i - 1} \times S^2T + A_{2, i} \times ST + A_{3, i - 1} \times T + S^3 \end{split}$$

$$\begin{split} A_{N - 1, i} &= A_{N - 2, i} \times S + A_{N - 1, i - 1} \times T \\ &= A_{0, i - 1} \times S^{N - 1} + A_{1, i - 1} \times S^{N-2}T + A_{2, i - 1} \times S^{N - 3}T + \cdots + A_{N, i - 1} \times T + S^N \\ &= A_{0, i - 1} \times S^{N - 1} + \sum_{j = 1}^{N - 1} A_{j, i - 1} \times S^{N - j} T + S^{N-1} \end{split}$$

由于 $0$ 号元素每次加 $1$，所以我们可以考虑在最后给表格加一行全为 $1$ 的元素作为 $N$ 行上的元素，接着可以把转移写成矩阵的形式。

那么我们有：

$$\left[ \begin{matrix} 1 & S & S^2 & S^3 & S^4 & \cdots & S^{N - 1} & 0\\ 0 & T & T \times S^1 & T \times S^2 & T \times S^3 & \cdots & T \times S^{N - 2} & 0 \\ 0 & 0 & T & T \times S^1 & T \times S^2 & \cdots & T \times S^{N - 3} & 0\\ 0 & 0 & 0 & T & T \times S^1 & \cdots & T \times S^{N - 4} & 0 \\ 0 & 0 & 0 & 0 & T & \cdots & T \times S^{N - 5} & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \cdots & T & 0\\ 1 & S & S^2 & S^3 & S^4 & \cdots & S^{N-1} & 1\\ \end{matrix} \right]$$

由于 $M$ 很大，对于每个查询 $(R_i, C_i)$，我们可以使用矩阵快速幂来计算出表格中 $C_i$ 上的所有元素。

整个算法时间复杂度：$\mathrm{O}(QN^3\log{M})$。

AC代码

#include <bits/stdc++.h>

namespace Matrix {
    template<class T>
    using Mat = std::vector<std::vector<T>>;

    template<class T>
    Mat<T> e(int n) {
        Mat<T> a(n, std::vector<T>(n, T()));
        for (int i = 0; i < n; ++i)
            a[i][i] = 1;
        return a;
    }

    template<class T>
    Mat<T> multi(const Mat<T> &a, const Mat<T> &b) {
        assert(!a.empty() and !b.empty() and a[0].size() == b.size());
        int n = a.size(), m = b.size(), p = b[0].size();
        Mat<T> c(n, std::vector<T>(m, T()));
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < m; ++k)
                for (int j = 0; j < p; ++j)
                    c[i][j] += a[i][k] * b[k][j];
        return c;
    }

    template<class T>
    Mat<T> pow(Mat<T> x, unsigned long long n) {
        assert(!x.empty() and x.size() == x[0].size());
        auto res = e<T>(x.size());
        while (n) {
            if (n & 1)
                res = multi(res, x);
            x = multi(x, x);
            n >>= 1;
        }
        return res;
    }

    template<class T>
    void print(Mat<T> mat) {
        if (mat.empty()) return;
        int n = mat.size(), m = mat[0].size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                std::cout << mat[i][j] << " \n"[j + 1 == m];
    }
}

template<int m>
class Modint {
private:
    unsigned int _v;
    static constexpr unsigned int umod() {return m;}
public:
    static constexpr int mod() {return m;}
    static Modint raw(int v) {
        Modint x;
        x._v = v;
        return x;
    }

    Modint() : _v(0) {}
    template<class T>
    Modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    unsigned int val() const {return _v;}

    Modint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    Modint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    Modint operator++(int) {
        Modint result = *this;
        ++*this;
        return result;
    }
    Modint operator--(int) {
        Modint result = *this;
        --*this;
        return result;
    }

    Modint& operator+=(const Modint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    Modint& operator-=(const Modint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    Modint& operator*=(const Modint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    Modint& operator/=(const Modint& rhs) {return *this = *this * rhs.inv();}

    Modint operator+() const {return *this;}
    Modint operator-() const {return Modint() - *this;}

    Modint pow(long long n) const {
        if (n < 0) return pow(-n).inv();
        Modint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    Modint inv() const {
        assert(_v);
        return pow(umod() - 2);
    }

    friend Modint operator+(const Modint& lhs, const Modint& rhs) {
        return Modint(lhs) += rhs;
    }
    friend Modint operator-(const Modint& lhs, const Modint& rhs) {
        return Modint(lhs) -= rhs;
    }
    friend Modint operator*(const Modint& lhs, const Modint& rhs) {
        return Modint(lhs) *= rhs;
    }
    friend Modint operator/(const Modint& lhs, const Modint& rhs) {
        return Modint(lhs) /= rhs;
    }
    friend bool operator==(const Modint& lhs, const Modint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const Modint& lhs, const Modint& rhs) {
        return lhs._v != rhs._v;
    }
};

using mint = Modint<998244353>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    Matrix::Mat<mint> dp = {std::vector<mint>(n + 1)};
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i) {
        int x; std::cin >> x;
        dp[0][i] = dp[0][i - 1] * s + 1LL * x * t;
    }
    dp[0][n] = 1;
    Matrix::Mat<mint> a = Matrix::e<mint>(n + 1);
    a[n][0] = 1;
    for (int i = 1; i < n; ++i) {
        a[i][i] = t;
        for (int j = i - 1; j >= 0; --j)
            a[j][i] = a[j + 1][i] * s;
        a[0][i] /= t;
        a[n][i] = a[n][i - 1] * s;
    }
    int q; std::cin >> q;
    while (q--) {
        int r, c;
        std::cin >> r >> c;
        auto res = Matrix::multi(dp, Matrix::pow(a, c - 1));
        std::cout << res[0][r].val() << '\n';
    }
    return 0;
}