#994611 (C++23) No.2810 Have Another Go (Hard)

提出ソース

結果

問題	No.2810 Have Another Go (Hard)
ユーザー	rniya
提出日時	2024-07-12 23:23:20
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	515 ms / 3,000 ms
コード長	8,076 bytes
コンパイル時間	3,325 ms
コンパイル使用メモリ	254,556 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-12 23:23:42
合計ジャッジ時間	22,715 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	362 ms 6,944 KB
testcase_02	AC	362 ms 6,940 KB
testcase_03	AC	366 ms 6,944 KB
testcase_04	AC	388 ms 6,944 KB
testcase_05	AC	361 ms 6,944 KB
testcase_06	AC	361 ms 6,940 KB
testcase_07	AC	368 ms 6,940 KB
testcase_08	AC	362 ms 6,944 KB
testcase_09	AC	361 ms 6,944 KB
testcase_10	AC	366 ms 6,944 KB
testcase_11	AC	4 ms 6,940 KB
testcase_12	AC	4 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	5 ms 6,944 KB
testcase_15	AC	4 ms 6,944 KB
testcase_16	AC	99 ms 6,944 KB
testcase_17	AC	417 ms 6,940 KB
testcase_18	AC	253 ms 6,940 KB
testcase_19	AC	389 ms 6,940 KB
testcase_20	AC	60 ms 6,944 KB
testcase_21	AC	133 ms 6,940 KB
testcase_22	AC	242 ms 6,940 KB
testcase_23	AC	175 ms 6,940 KB
testcase_24	AC	299 ms 6,940 KB
testcase_25	AC	485 ms 6,940 KB
testcase_26	AC	487 ms 6,944 KB
testcase_27	AC	498 ms 6,944 KB
testcase_28	AC	487 ms 6,940 KB
testcase_29	AC	515 ms 6,940 KB
testcase_30	AC	488 ms 6,940 KB
testcase_31	AC	489 ms 6,940 KB
testcase_32	AC	487 ms 6,940 KB
testcase_33	AC	490 ms 6,944 KB
testcase_34	AC	487 ms 6,944 KB
testcase_35	AC	488 ms 6,944 KB
testcase_36	AC	487 ms 6,944 KB
testcase_37	AC	488 ms 6,940 KB
testcase_38	AC	487 ms 6,944 KB
testcase_39	AC	490 ms 6,940 KB
testcase_40	AC	487 ms 6,944 KB
testcase_41	AC	488 ms 6,944 KB
testcase_42	AC	488 ms 6,940 KB
testcase_43	AC	513 ms 6,944 KB
testcase_44	AC	489 ms 6,940 KB
testcase_45	AC	488 ms 6,940 KB
testcase_46	AC	2 ms 6,944 KB
testcase_47	AC	3 ms 6,944 KB
testcase_48	AC	4 ms 6,940 KB
testcase_49	AC	3 ms 6,940 KB
testcase_50	AC	3 ms 6,944 KB
testcase_51	AC	60 ms 6,940 KB
testcase_52	AC	38 ms 6,940 KB
testcase_53	AC	87 ms 6,940 KB
testcase_54	AC	115 ms 6,940 KB
testcase_55	AC	43 ms 6,940 KB
testcase_56	AC	105 ms 6,944 KB
testcase_57	AC	76 ms 6,944 KB
testcase_58	AC	58 ms 6,944 KB
testcase_59	AC	144 ms 6,940 KB
testcase_60	AC	87 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード