結果

問題 No.2807 Have Another Go (Easy)
ユーザー rniyarniya
提出日時 2024-07-12 23:22:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 235 ms / 3,000 ms
コード長 8,076 bytes
コンパイル時間 2,855 ms
コンパイル使用メモリ 254,328 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-12 23:22:57
合計ジャッジ時間 10,148 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

#include <atcoder/modint>

template <typename T, int N> struct SquareMatrix {
    std::array<std::array<T, N>, N> A;

    SquareMatrix() : A() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                A[i][j] = T(0);
            }
        }
    }

    int size() const { return N; }

    inline const std::array<T, N>& operator[](int i) const { return A[i]; }

    inline std::array<T, N>& operator[](int i) { return A[i]; }

    static SquareMatrix identity() {
        SquareMatrix res;
        for (int i = 0; i < N; i++) res[i][i] = 1;
        return res;
    }

    SquareMatrix& operator+=(const SquareMatrix& B) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                (*this)[i][j] += B[i][j];
            }
        }
        return *this;
    }

    SquareMatrix& operator-=(const SquareMatrix& B) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                (*this)[i][j] -= B[i][j];
            }
        }
        return *this;
    }

    SquareMatrix& operator*=(const SquareMatrix& B) {
        std::array<std::array<T, N>, N> C;
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                for (int j = 0; j < N; j++) {
                    C[i][j] += (*this)[i][k] * B[k][j];
                }
            }
        }
        std::swap(A, C);
        return *this;
    }

    SquareMatrix& operator*=(const T& v) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                (*this)[i][j] *= v;
            }
        }
        return *this;
    }

    SquareMatrix& operator/=(const T& v) {
        T inv = T(1) / v;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                (*this)[i][j] *= inv;
            }
        }
        return *this;
    }

    SquareMatrix operator-() const {
        SquareMatrix res;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res[i][j] = -(*this)[i][j];
            }
        }
        return res;
    }

    SquareMatrix operator+(const SquareMatrix& B) const { return SquareMatrix(*this) += B; }

    SquareMatrix operator-(const SquareMatrix& B) const { return SquareMatrix(*this) -= B; }

    SquareMatrix operator*(const SquareMatrix& B) const { return SquareMatrix(*this) *= B; }

    SquareMatrix operator*(const T& v) const { return SquareMatrix(*this) *= v; }

    SquareMatrix operator/(const T& v) const { return SquareMatrix(*this) /= v; }

    bool operator==(const SquareMatrix& B) const { return A == B.A; }

    bool operator!=(const SquareMatrix& B) const { return A != B.A; }

    SquareMatrix pow(long long n) const {
        assert(0 <= n);
        SquareMatrix x = *this, r = identity();
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    SquareMatrix transpose() const {
        SquareMatrix res;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res[j][i] = (*this)[i][j];
            }
        }
        return res;
    }

    int rank() const { return SquareMatrix(*this).gauss_jordan().first; }

    T det() const { return SquareMatrix(*this).gauss_jordan().second; }

    SquareMatrix inv() const {
        SquareMatrix B(*this), C = identity();
        for (int j = 0; j < N; j++) {
            int pivot = -1;
            for (int i = j; i < N; i++) {
                if (B[i][j] != T(0)) {
                    pivot = i;
                    break;
                }
            }
            assert(pivot != -1);
            if (pivot != j) {
                std::swap(B[pivot], B[j]);
                std::swap(C[pivot], C[j]);
            }
            {
                T coef = T(1) / B[j][j];
                for (int k = 0; k < N; k++) {
                    B[j][k] *= coef;
                    C[j][k] *= coef;
                }
            }
            for (int i = 0; i < N; i++) {
                if (i == j) continue;
                T coef = B[i][j];
                if (coef == T(0)) continue;
                for (int k = 0; k < N; k++) {
                    B[i][k] -= B[j][k] * coef;
                    C[i][k] -= C[j][k] * coef;
                }
            }
        }
        return C;
    }

    friend std::ostream& operator<<(std::ostream& os, const SquareMatrix& p) {
        os << "[(" << N << " * " << N << " Matrix)";
        os << "\n[columun sums: ";
        for (int j = 0; j < N; j++) {
            T sum = 0;
            for (int i = 0; i < N; i++) sum += p[i][j];
            ;
            os << sum << (j + 1 < N ? "," : "");
        }
        os << "]";
        for (int i = 0; i < N; i++) {
            os << "\n[";
            for (int j = 0; j < N; j++) os << p[i][j] << (j + 1 < N ? "," : "");
            os << "]";
        }
        os << "]\n";
        return os;
    }

  private:
    std::pair<int, T> gauss_jordan() {
        int rank = 0;
        T det = 1;
        for (int j = 0; j < N; j++) {
            int pivot = -1;
            for (int i = rank; i < N; i++) {
                if ((*this)[i][j] != T(0)) {
                    pivot = i;
                    break;
                }
            }
            if (pivot == -1) {
                det = 0;
                continue;
            }
            if (pivot != rank) {
                det = -det;
                std::swap((*this)[pivot], (*this)[rank]);
            }
            det *= A[rank][j];
            if (A[rank][j] != T(1)) {
                T coef = T(1) / (*this)[rank][j];
                for (int k = j; k < N; k++) (*this)[rank][k] *= coef;
            }
            for (int i = 0; i < N; i++) {
                if (i == rank) continue;
                T coef = (*this)[i][j];
                if (coef == T(0)) continue;
                for (int k = j; k < N; k++) (*this)[i][k] -= (*this)[rank][k] * coef;
            }
            rank++;
        }
        return {rank, det};
    }
};

using ll = long long;

using namespace std;

const int MAX = 6;
using mint = atcoder::modint998244353;
using SM = SquareMatrix<mint, MAX>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N, M, K;
    cin >> N >> M >> K;

    SM m1, m2;
    for (int i = 0; i + 1 < MAX; i++) m1[i + 1][i] = m2[i + 1][i] = 1;
    for (int i = 0; i < MAX; i++) m1[i][MAX - 1] = 1;
    mint tot = 0;
    auto TOT = m1.pow(1LL * N * M - 1);
    for (int i = 0; i < MAX; i++) tot += TOT[MAX - 1][i] * (i + 1);
    auto query = [&](int C) -> mint {
        SM m = SM::identity();
        m *= m1.pow(C - 1);
        m *= m2;
        m *= (m1.pow(N - 1) * m2).pow(M - 1);
        m *= m1.pow(N - 1 - C);
        mint res = tot;
        for (int i = 0; i < MAX; i++) res -= m[MAX - 1][i] * (i + 1);
        return res;
    };

    for (; K--;) {
        int C;
        cin >> C;
        cout << query(C).val() << "\n";
    }
    return 0;
}
0