結果

問題 No.2435 Order All Company
ユーザー sotanishysotanishy
提出日時 2023-08-18 22:32:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 9,288 bytes
コンパイル時間 2,802 ms
コンパイル使用メモリ 211,084 KB
実行使用メモリ 5,932 KB
最終ジャッジ日時 2023-08-18 22:32:56
合計ジャッジ時間 4,809 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 53 ms
5,760 KB
testcase_06 AC 52 ms
5,924 KB
testcase_07 AC 25 ms
4,376 KB
testcase_08 AC 44 ms
5,620 KB
testcase_09 AC 54 ms
5,840 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 41 ms
5,784 KB
testcase_15 AC 47 ms
5,932 KB
testcase_16 AC 29 ms
5,812 KB
testcase_17 AC 43 ms
5,564 KB
testcase_18 AC 23 ms
5,416 KB
testcase_19 AC 14 ms
5,148 KB
testcase_20 AC 22 ms
5,836 KB
testcase_21 AC 22 ms
5,788 KB
testcase_22 AC 47 ms
5,792 KB
testcase_23 AC 10 ms
4,376 KB
testcase_24 AC 21 ms
5,540 KB
testcase_25 AC 38 ms
5,692 KB
testcase_26 AC 29 ms
5,448 KB
testcase_27 AC 42 ms
5,592 KB
testcase_28 AC 20 ms
5,600 KB
testcase_29 AC 32 ms
5,876 KB
testcase_30 AC 23 ms
5,452 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 1 ms
4,380 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 4 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

template <int mod>
class Modint {
    using mint = Modint;
    static_assert(mod > 0, "Modulus must be positive");

   public:
    static constexpr int get_mod() noexcept { return mod; }

    constexpr Modint(long long y = 0) noexcept
        : x(y >= 0 ? y % mod : (y % mod + mod) % mod) {}

    constexpr int value() const noexcept { return x; }

    constexpr mint& operator+=(const mint& r) noexcept {
        if ((x += r.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator-=(const mint& r) noexcept {
        if ((x += mod - r.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator*=(const mint& r) noexcept {
        x = static_cast<int>(1LL * x * r.x % mod);
        return *this;
    }
    constexpr mint& operator/=(const mint& r) noexcept {
        *this *= r.inv();
        return *this;
    }

    constexpr mint operator-() const noexcept { return mint(-x); }

    constexpr mint operator+(const mint& r) const noexcept {
        return mint(*this) += r;
    }
    constexpr mint operator-(const mint& r) const noexcept {
        return mint(*this) -= r;
    }
    constexpr mint operator*(const mint& r) const noexcept {
        return mint(*this) *= r;
    }
    constexpr mint operator/(const mint& r) const noexcept {
        return mint(*this) /= r;
    }

    constexpr bool operator==(const mint& r) const noexcept { return x == r.x; }
    constexpr bool operator!=(const mint& r) const noexcept { return x != r.x; }

    constexpr mint inv() const noexcept {
        int a = x, b = mod, u = 1, v = 0;
        while (b > 0) {
            int t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * v, v);
        }
        return mint(u);
    }

    constexpr mint pow(long long n) const noexcept {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend std::ostream& operator<<(std::ostream& os, const mint& r) {
        return os << r.x;
    }

    friend std::istream& operator>>(std::istream& is, mint& r) {
        long long t;
        is >> t;
        r = mint(t);
        return is;
    }

   private:
    int x;
};

using mint = Modint<998244353>;

template <typename T>
class Matrix {
   public:
    static Matrix concat(const Matrix& A, const Matrix& B) {
        assert(A.m == B.m);
        Matrix C(A.m, A.n + B.n);
        for (int i = 0; i < A.m; ++i) {
            std::copy(A[i].begin(), A[i].end(), C[i].begin());
            std::copy(B[i].begin(), B[i].end(), C[i].begin() + A.n);
        }
        return C;
    }

    Matrix() = default;
    Matrix(int m, int n) : mat(m, std::vector<T>(n)), m(m), n(n) {}
    Matrix(std::initializer_list<std::initializer_list<T>> list) {
        for (auto& l : list) mat.emplace_back(l);
        m = mat.size();
        n = mat[0].size();
    }

    int row() const { return m; }
    int col() const { return n; }

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

    Matrix& operator+=(const Matrix& rhs) {
        assert(m == rhs.m && n == rhs.n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] += rhs[i][j];
            }
        }
        return *this;
    }

    Matrix& operator-=(const Matrix& rhs) {
        assert(m == rhs.m && n == rhs.n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] -= rhs[i][j];
            }
        }
        return *this;
    }

    Matrix operator+(const Matrix& rhs) const { return Matrix(*this) += rhs; }
    Matrix operator-(const Matrix& rhs) const { return Matrix(*this) -= rhs; }

    Matrix transpose() const {
        Matrix ret(n, m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                ret[i][j] = mat[j][i];
            }
        }
        return ret;
    }

    Matrix matmul(const Matrix& B) const {
        assert(n == B.m);
        Matrix ret(m, B.n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < B.n; ++j) {
                for (int k = 0; k < n; ++k) {
                    ret[i][j] += mat[i][k] * B[k][j];
                }
            }
        }
        return ret;
    }

    Matrix rref() const {
        Matrix A(*this);
        int pivot = 0;
        for (int j = 0; j < n; ++j) {
            int i = pivot;
            while (i < m && eq(A[i][j], T(0))) ++i;
            if (i == m) continue;

            if (i != pivot) A[i].swap(A[pivot]);

            T p = A[pivot][j];
            for (int l = j; l < n; ++l) A[pivot][l] /= p;

            for (int k = 0; k < m; ++k) {
                if (k == pivot) continue;
                T v = A[k][j];
                for (int l = j; l < n; ++l) {
                    A[k][l] -= A[pivot][l] * v;
                }
            }

            ++pivot;
        }
        return A;
    }

    int rank() const {
        auto A = rref();
        for (int i = 0; i < m; ++i) {
            bool nonzero = false;
            for (int j = 0; j < n; ++j) {
                if (!eq(A[i][j], T(0))) {
                    nonzero = true;
                    break;
                }
            }
            if (!nonzero) return i;
        }
        return m;
    }

    template <typename U,
              typename std::enable_if<std::is_floating_point<U>::value>::type* =
                  nullptr>
    static constexpr bool eq(U a, U b) {
        return std::abs(a - b) < 1e-8;
    }

    template <typename U, typename std::enable_if<!std::is_floating_point<
                              U>::value>::type* = nullptr>
    static constexpr bool eq(U a, U b) {
        return a == b;
    }

   protected:
    std::vector<std::vector<T>> mat;
    int m, n;
};

template <typename T>
class SquareMatrix : public Matrix<T> {
    using Matrix<T>::Matrix;
    using Matrix<T>::eq;
    using Matrix<T>::n;

   public:
    static SquareMatrix I(int n) {
        SquareMatrix ret(n);
        for (int i = 0; i < n; ++i) ret[i][i] = 1;
        return ret;
    }

    SquareMatrix() = default;
    explicit SquareMatrix(int n) : Matrix<T>(n, n) {}
    SquareMatrix(const Matrix<T>& mat) : Matrix<T>(mat) {
        assert(Matrix<T>::m == n);
    }
    SquareMatrix(std::initializer_list<std::initializer_list<T>> list)
        : Matrix<T>(list) {
        assert(Matrix<T>::m == n);
    }

    SquareMatrix pow(long long k) const {
        auto ret = I(n);
        auto A(*this);
        while (k > 0) {
            if (k & 1) ret = ret.matmul(A);
            A = A.matmul(A);
            k >>= 1;
        }
        return ret;
    }

    T det() const {
        SquareMatrix A(*this);
        T ret = 1;
        for (int j = 0; j < n; ++j) {
            int i = j;
            while (i < n && eq(A[i][j], T(0))) ++i;
            if (i == n) return 0;

            if (i != j) {
                A[i].swap(A[j]);
                ret = -ret;
            }

            T p = A[j][j];
            ret *= p;
            for (int l = j; l < n; ++l) A[j][l] /= p;

            for (int k = j + 1; k < n; ++k) {
                T v = A[k][j];
                for (int l = j; l < n; ++l) {
                    A[k][l] -= A[j][l] * v;
                }
            }
        }
        return ret;
    }

    SquareMatrix inv() const {
        assert(!eq(det(), T(0)));
        auto IB = Matrix<T>::concat(*this, I(n)).rref();
        SquareMatrix B(n);
        for (int i = 0; i < n; ++i) {
            std::copy(IB[i].begin() + n, IB[i].end(), B[i].begin());
        }
        return B;
    }
};

using Mat = SquareMatrix<mint>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N, K;
    cin >> N >> K;
    vector<vector<pair<int, int>>> edges(K);
    rep(i, 0, K) {
        int t;
        cin >> t;
        rep(_, 0, t) {
            int a, b;
            cin >> a >> b;
            --a, --b;
            edges[i].push_back({a, b});
        }
    }

    auto calc = [&](vector<pair<int, int>>& edges) {
        Mat mat(N - 1);
        for (auto [a, b] : edges) {
            if (a > b) swap(a, b);
            if (a != N - 1) mat[a][a] += 1;
            if (b != N - 1) mat[b][b] += 1;
            if (a != N - 1 && b != N - 1) {
                mat[a][b] -= 1;
                mat[b][a] -= 1;
            }
        }
        return mat.det();
    };

    mint ans = 0;
    rep(S, 1, 1 << K) {
        vector<pair<int, int>> use;
        rep(i, 0, K) {
            if (S >> i & 1) {
                for (auto [a, b] : edges[i]) use.push_back({a, b});
            }
        }
        ans += __builtin_popcount(S) % 2 == K % 2 ? calc(use) : -calc(use);
    }
    cout << ans << endl;
}
0