#868011 (C++17) No.2255 Determinant Sum

提出ソース

結果

問題	No.2255 Determinant Sum
ユーザー	suisen
提出日時	2023-05-11 18:14:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	29 ms / 2,000 ms
コード長	10,466 bytes
コンパイル時間	999 ms
コンパイル使用メモリ	101,504 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-05 16:14:41
合計ジャッジ時間	2,109 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	29 ms 5,376 KB
testcase_07	AC	22 ms 5,376 KB
testcase_08	AC	16 ms 5,376 KB
testcase_09	AC	18 ms 5,376 KB
testcase_10	AC	22 ms 5,376 KB
testcase_11	AC	8 ms 5,376 KB
testcase_12	AC	10 ms 5,376 KB
testcase_13	AC	7 ms 5,376 KB
testcase_14	AC	28 ms 5,376 KB
testcase_15	AC	12 ms 5,376 KB
testcase_16	AC	13 ms 5,376 KB
testcase_17	AC	14 ms 5,376 KB
testcase_18	AC	8 ms 5,376 KB
testcase_19	AC	8 ms 5,376 KB
testcase_20	AC	10 ms 5,376 KB
testcase_21	AC	10 ms 5,376 KB
testcase_22	AC	9 ms 5,376 KB

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

ソースコード

raw source code

#include <iostream>
#include <map>

#include <atcoder/dsu>
#include <atcoder/modint>

using mint = atcoder::modint;

namespace atcoder {
    std::istream& operator>>(std::istream& in, mint& a) {
        long long e; in >> e; a = e;
        return in;
    }

    std::ostream& operator<<(std::ostream& out, const mint& a) {
        out << a.val();
        return out;
    }
} // namespace atcoder

#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>

namespace suisen {
    template <typename T>
    struct Matrix {
        std::vector<std::vector<T>> dat;

        Matrix() {}
        Matrix(int n) : Matrix(n, n) {}
        Matrix(int n, int m, T fill_value = T(0)) : dat(n, std::vector<T>(m, fill_value)) {}
        Matrix(const std::vector<std::vector<T>>& dat) : dat(dat) {}

        const std::vector<T>& operator[](int i) const { return dat[i]; }
        std::vector<T>& operator[](int i) { return dat[i]; }

        operator std::vector<std::vector<T>>() const { return dat; }

        friend bool operator==(const Matrix<T>& A, const Matrix<T>& B) { return A.dat == B.dat; }
        friend bool operator!=(const Matrix<T>& A, const Matrix<T>& B) { return A.dat != B.dat; }

        std::pair<int, int> shape() const { return dat.empty() ? std::make_pair<int, int>(0, 0) : std::make_pair<int, int>(dat.size(), dat[0].size()); }
        int row_size() const { return dat.size(); }
        int col_size() const { return dat.empty() ? 0 : dat[0].size(); }

        friend Matrix<T>& operator+=(Matrix<T>& A, const Matrix<T>& B) {
            assert(A.shape() == B.shape());
            auto [n, m] = A.shape();
            for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) A.dat[i][j] += B.dat[i][j];
            return A;
        }
        friend Matrix<T>& operator-=(Matrix<T>& A, const Matrix<T>& B) {
            assert(A.shape() == B.shape());
            auto [n, m] = A.shape();
            for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) A.dat[i][j] -= B.dat[i][j];
            return A;
        }
        friend Matrix<T>& operator*=(Matrix<T>& A, const Matrix<T>& B) { return A = A * B; }
        friend Matrix<T>& operator*=(Matrix<T>& A, const T& val) {
            for (auto& row : A.dat) for (auto& elm : row) elm *= val;
            return A;
        }
        friend Matrix<T>& operator/=(Matrix<T>& A, const T& val) { return A *= T(1) / val; }
        friend Matrix<T>& operator/=(Matrix<T>& A, const Matrix<T>& B) { return A *= B.inv(); }

        friend Matrix<T> operator+(Matrix<T> A, const Matrix<T>& B) { A += B; return A; }
        friend Matrix<T> operator-(Matrix<T> A, const Matrix<T>& B) { A -= B; return A; }
        friend Matrix<T> operator*(const Matrix<T>& A, const Matrix<T>& B) {
            assert(A.col_size() == B.row_size());
            const int n = A.row_size(), m = A.col_size(), l = B.col_size();

            if (std::min({ n, m, l }) <= 70) {
                // naive
                Matrix<T> C(n, l);
                for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (int k = 0; k < l; ++k) {
                    C.dat[i][k] += A.dat[i][j] * B.dat[j][k];
                }
                return C;
            }

            // strassen
            const int nl = 0, nm = n >> 1, nr = nm + nm;
            const int ml = 0, mm = m >> 1, mr = mm + mm;
            const int ll = 0, lm = l >> 1, lr = lm + lm;

            auto A00 = A.submatrix(nl, nm, ml, mm), A01 = A.submatrix(nl, nm, mm, mr);
            auto A10 = A.submatrix(nm, nr, ml, mm), A11 = A.submatrix(nm, nr, mm, mr);

            auto B00 = B.submatrix(ml, mm, ll, lm), B01 = B.submatrix(ml, mm, lm, lr);
            auto B10 = B.submatrix(mm, mr, ll, lm), B11 = B.submatrix(mm, mr, lm, lr);

            auto P0 = (A00 + A11) * (B00 + B11);
            auto P1 = (A10 + A11) * B00;
            auto P2 = A00 * (B01 - B11);
            auto P3 = A11 * (B10 - B00);
            auto P4 = (A00 + A01) * B11;
            auto P5 = (A10 - A00) * (B00 + B01);
            auto P6 = (A01 - A11) * (B10 + B11);

            Matrix<T> C(n, l);

            C.assign_submatrix(nl, ll, P0 + P3 - P4 + P6), C.assign_submatrix(nl, lm, P2 + P4);
            C.assign_submatrix(nm, ll, P1 + P3), C.assign_submatrix(nm, lm, P0 + P2 - P1 + P5);

            // fractions
            if (l != lr) {
                for (int i = 0; i < nr; ++i) for (int j = 0; j < mr; ++j) C.dat[i][lr] += A.dat[i][j] * B.dat[j][lr];
            }
            if (m != mr) {
                for (int i = 0; i < nr; ++i) for (int k = 0; k < l; ++k) C.dat[i][k] += A.dat[i][mr] * B.dat[mr][k];
            }
            if (n != nr) {
                for (int j = 0; j < m; ++j) for (int k = 0; k < l; ++k) C.dat[nr][k] += A.dat[nr][j] * B.dat[j][k];
            }

            return C;
        }
        friend Matrix<T> operator*(const T& val, Matrix<T> A) { A *= val; return A; }
        friend Matrix<T> operator*(Matrix<T> A, const T& val) { A *= val; return A; }
        friend Matrix<T> operator/(const Matrix<T>& A, const Matrix<T>& B) { return A * B.inv(); }
        friend Matrix<T> operator/(Matrix<T> A, const T& val) { A /= val; return A; }
        friend Matrix<T> operator/(const T& val, const Matrix<T>& A) { return val * A.inv(); }

        friend std::vector<T> operator*(const Matrix<T>& A, const std::vector<T>& x) {
            const auto [n, m] = A.shape();
            assert(m == int(x.size()));
            std::vector<T> b(n, T(0));
            for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) b[i] += A.dat[i][j] * x[j];
            return b;
        }

        static Matrix<T> e0(int n) { return Matrix<T>(n, Identity::ADD); }
        static Matrix<T> e1(int n) { return Matrix<T>(n, Identity::MUL); }

        Matrix<T> pow(long long b) const {
            assert_square();
            assert(b >= 0);
            Matrix<T> res = e1(row_size()), p = *this;
            for (; b; b >>= 1) {
                if (b & 1) res *= p;
                p *= p;
            }
            return res;
        }
        Matrix<T> inv() const { return *safe_inv(); }

        std::optional<Matrix<T>> safe_inv() const {
            assert_square();
            Matrix<T> A = *this;
            const int n = A.row_size();
            for (int i = 0; i < n; ++i) {
                A[i].resize(2 * n, T{ 0 });
                A[i][n + i] = T{ 1 };
            }
            for (int i = 0; i < n; ++i) {
                for (int k = i; k < n; ++k) if (A[k][i] != T{ 0 }) {
                    std::swap(A[i], A[k]);
                    T c = T{ 1 } / A[i][i];
                    for (int j = i; j < 2 * n; ++j) A[i][j] *= c;
                    break;
                }
                if (A[i][i] == T{ 0 }) return std::nullopt;
                for (int k = 0; k < n; ++k) if (k != i and A[k][i] != T{ 0 }) {
                    T c = A[k][i];
                    for (int j = i; j < 2 * n; ++j) A[k][j] -= c * A[i][j];
                }
            }
            for (auto& row : A.dat) row.erase(row.begin(), row.begin() + n);
            return A;
        }

        T det() const {
            assert_square();
            Matrix<T> A = *this;
            bool sgn = false;
            const int n = A.row_size();
            for (int j = 0; j < n; ++j) for (int i = j + 1; i < n; ++i) if (A[i][j] != T{ 0 }) {
                std::swap(A[j], A[i]);
                T q = A[i][j] / A[j][j];
                for (int k = j; k < n; ++k) A[i][k] -= A[j][k] * q;
                sgn = not sgn;
            }
            T res = sgn ? T{ -1 } : T{ +1 };
            for (int i = 0; i < n; ++i) res *= A[i][i];
            return res;
        }
        T det_arbitrary_mod() const {
            assert_square();
            Matrix<T> A = *this;
            bool sgn = false;
            const int n = A.row_size();
            for (int j = 0; j < n; ++j) for (int i = j + 1; i < n; ++i) {
                for (; A[i][j].val(); sgn = not sgn) {
                    std::swap(A[j], A[i]);
                    T q = A[i][j].val() / A[j][j].val();
                    for (int k = j; k < n; ++k) A[i][k] -= A[j][k] * q;
                }
            }
            T res = sgn ? -1 : +1;
            for (int i = 0; i < n; ++i) res *= A[i][i];
            return res;
        }
        void assert_square() const { assert(row_size() == col_size()); }

        Matrix<T> submatrix(int row_begin, int row_end, int col_begin, int col_end) const {
            Matrix<T> A(row_end - row_begin, col_end - col_begin);
            for (int i = row_begin; i < row_end; ++i) for (int j = col_begin; j < col_end; ++j) {
                A[i - row_begin][j - col_begin] = dat[i][j];
            }
            return A;
        }
        void assign_submatrix(int row_begin, int col_begin, const Matrix<T>& A) {
            const int n = A.row_size(), m = A.col_size();
            assert(row_begin + n <= row_size() and col_begin + m <= col_size());
            for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
                dat[row_begin + i][col_begin + j] = A[i][j];
            }
        }
    private:
        enum class Identity {
            ADD, MUL
        };
        Matrix(int n, Identity ident) : Matrix<T>::Matrix(n) {
            if (ident == Identity::MUL) for (int i = 0; i < n; ++i) dat[i][i] = 1;
        }
    };
} // namespace suisen

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

    int t;
    std::cin >> t;
    while (t --> 0) {
        int n, p;
        std::cin >> n >> p;

        mint::set_mod(p);

        suisen::Matrix<int> a(n, n);
        std::vector<int> cnt_row(n), cnt_col(n);
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            std::cin >> a[i][j];
            if (a[i][j] == -1) {
                ++cnt_row[i], ++cnt_col[j];
            }
        }

        if (p != 2 or *std::max_element(cnt_row.begin(), cnt_row.end()) > 1 or *std::max_element(cnt_col.begin(), cnt_col.end()) > 1) {
            std::cout << 0 << '\n';
        } else {
            std::vector<std::vector<mint>> b;
            for (int i = 0; i < n; ++i) if (cnt_row[i] == 0) {
                auto &row = b.emplace_back();
                for (int j = 0; j < n; ++j) if (cnt_col[j] == 0) {
                    row.push_back(a[i][j]);
                }
            }
            std::cout << suisen::Matrix<mint>(b).det() << '\n';
        }
    }
}

yukicoder

結果

テストケース

ソースコード