#1196977 (C++23) No.1303 Inconvenient Kingdom

• 問題: No.1303 Inconvenient Kingdom
• ユーザー: iastm
• 提出日時: 2026-11-05 02:46:38
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 7 ms / 3,000 ms
• コード長: 12,022 bytes
• コンパイル時間: 2,008 ms
• コンパイル使用メモリ: 209,436 KB
• 実行使用メモリ: 9,908 KB
• 最終ジャッジ日時: 2026-11-05 02:46:54
• 合計ジャッジ時間: 4,561 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 4
other	AC * 34

ソースコード

#include <iostream>
#include <vector>
#include <atcoder/dsu>
#include <atcoder/modint>
// #include <kotone/matrix>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_MATRIX_HPP
#define KOTONE_MATRIX_HPP 1

#include <vector>
#include <cassert>
// #include <kotone/internal_type_traits>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_INTERNAL_TYPE_TRAITS_HPP
#define KOTONE_INTERNAL_TYPE_TRAITS_HPP 1

#include <concepts>

namespace kotone {

template <typename T> concept number = std::is_arithmetic_v<T>;

template <typename T> concept signed_number = std::signed_integral<T> || std::floating_point<T>;

template <typename mint> concept compatible_modint = requires(mint a, mint b, int64_t x) {
    { mint::mod() } -> std::convertible_to<int>;
    mint{};
    mint{1};
    mint{x};

    { a + b }       -> std::same_as<mint>;
    { a - b }       -> std::same_as<mint>;
    { -a }          -> std::same_as<mint>;
    { a * b }       -> std::same_as<mint>;
    { a / b }       -> std::same_as<mint>;
    { a.inv() }     -> std::same_as<mint>;
    { a.pow(x) }    -> std::same_as<mint>;

    { a += b }      -> std::same_as<mint&>;
    { a -= b }      -> std::same_as<mint&>;
    { a *= b }      -> std::same_as<mint&>;
    { a /= b }      -> std::same_as<mint&>;

    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
    { a.val() }     -> std::convertible_to<int>;
};

template <typename T> concept additive = requires(T a, T b) {
    T{};
    { a + b }       -> std::same_as<T>;
    { a - b }       -> std::same_as<T>;
    { -a }          -> std::same_as<T>;
    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
};

template <typename T> concept mutable_additive = (
    additive<T>
    && requires(T a, T b) {
        { a += b }  -> std::same_as<T&>;
        { a -= b }  -> std::same_as<T&>;
        { ++a }     -> std::same_as<T&>;
        { --a }     -> std::same_as<T&>;
        { a++ }     -> std::same_as<T>;
        { a-- }     -> std::same_as<T>;
    }
);

}  // namespace kotone

#endif  // KOTONE_INTERNAL_TYPE_TRAITS

namespace kotone {

namespace matrix {

template <compatible_modint mint> using matrix = std::vector<std::vector<mint>>;

// Returns the identity matrix of the specified dimension.
template <compatible_modint mint> matrix<mint> identity(int dimension) {
    assert(dimension >= 0);
    std::vector result(dimension, std::vector<mint>(dimension));
    for (int i = 0; i < dimension; i++) result[i][i] = 1;
    return result;
}

// Returns the product of two matrices.
// Requires `a` and `b` to be valid matrices.
// Requires the product to exist.
template <compatible_modint mint> matrix<mint> prod(const matrix<mint> &a, const matrix<mint> &b) {
    if (a.empty() && b.empty()) return {};
    assert(!a.empty() && !b.empty() && a[0].size() == b.size());
    int n = a.size(), m = b.size(), l = b[0].size();
    std::vector result(n, std::vector<mint>(l));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            for (int j = 0; j < l; j++) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return result;
}

// Returns the matrix raised to the specified exponent `k`.
// Requires `mat` to be a square matrix.
template <compatible_modint mint> matrix<mint> pow(const matrix<mint> &mat, int64_t k) {
    // assert(k >= 0);
    if (k == 0) return identity<mint>(mat.size());
    if (k == 1) return mat;
    matrix<mint> result = pow(mat, k / 2);
    result = prod(result, result);
    if (k % 2 == 1) result = prod(result, mat);
    return result;
}

// Returns a basis of the specified matrix.
// Requires `mat` to be a valid matrix.
template <compatible_modint mint> matrix<mint> basis(matrix<mint> mat) {
    if (mat.empty()) return {};
    int n = mat.size(), m = mat[0].size();
    int r = 0;
    for (int k = 0, j = 0; k < n && j < m; k++, j++, r++) {
        while (j < m) {
            for (int i = k; i < n; i++) {
                if (mat[i][k] == 0) continue;
                if (i != k) std::swap(mat[i], mat[k]);
                break;
            }
            if (mat[k][j] != 0) break;
            j++;
        }
        if (j == m) break;
        mint inv = mat[k][j].inv();
        for (int nj = 0; nj < m; nj++) mat[k][nj] *= inv;
        for (int i = k + 1; i < n; i++) {
            for (int nj = m - 1; nj >= j; nj--) mat[i][nj] -= mat[i][j] * mat[k][nj];
        }
    }
    mat.resize(r);
    return mat;
}

// Returns the determinant specified matrix.
// Requires `mat` to be a square matrix.
template <compatible_modint mint> mint det(matrix<mint> mat) {
    int n = mat.size();
    mint result = 1;
    for (int k = 0; k < n; k++) {
        for (int i = k; i < n; i++) {
            if (mat[i][k] == 0) continue;
            if (i != k) {
                std::swap(mat[i], mat[k]);
                result = -result;
            }
            break;
        }
        if (mat[k][k] == 0) return 0;
        result *= mat[k][k];
        mint inv = mat[k][k].inv();
        for (int j = 0; j < n; j++) mat[k][j] *= inv;
        for (int i = k + 1; i < n; i++) {
            for (int j = n - 1; j >= k; j--) mat[i][j] -= mat[i][k] * mat[k][j];
        }
    }
    return result;
}

// Returns a pair `{inv, found}` representing the inverse of the matrix such that
// - `inv` is the inverse matrix and `found == true` if the inverse exists, or
// - `inv` is empty and `found == false` if the inverse does not exist.
//
// Requires `mat` to be a square matrix.
template <compatible_modint mint> std::pair<matrix<mint>, bool> inv(matrix<mint> mat) {
    int n = mat.size();
    for (int i = 0; i < n; i++) {
        mat[i].resize(n * 2);
        mat[i][i + n] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = k; i < n; i++) {
            if (mat[i][k] == 0) continue;
            if (i != k) std::swap(mat[i], mat[k]);
            break;
        }
        if (mat[k][k] == 0) return {{}, false};
        mint inv = mat[k][k].inv();
        for (int j = 0; j < n * 2; j++) mat[k][j] *= inv;
        for (int i = 0; i < n; i++) {
            if (i == k) continue;
            for (int j = n * 2 - 1; j >= k; j--) mat[i][j] -= mat[i][k] * mat[k][j];
        }
    }
    for (int i = 0; i < n; i++) mat[i].erase(mat[i].begin(), mat[i].begin() + n);
    return {mat, true};
}

// Returns the upper Hessenberg form of the specified matrix.
// Requires `mat` to be a square matrix.
// Reference: https://judge.yosupo.jp/problem/characteristic_polynomial
template <compatible_modint mint> matrix<mint> upper_hessenberg(matrix<mint> mat) {
    int n = mat.size();
    for (int k = 0; k < n - 2; k++) {
        for (int i = k + 1; i < n; i++) {
            if (mat[i][k] == 0) continue;
            if (i != k + 1) {
                std::swap(mat[i], mat[k + 1]);
                for (int ni = 0; ni < n; ni++) std::swap(mat[ni][i], mat[ni][k + 1]);
            }
            break;
        }
        if (mat[k + 1][k] == 0) continue;
        mint inv = mat[k + 1][k].inv();
        for (int i = k + 2; i < n; i++) {
            mint acc = mat[i][k] * inv;
            for (int j = k; j < n; j++) mat[i][j] -= acc * mat[k + 1][j];
            for (int j = 0; j < n; j++) mat[j][k + 1] += acc * mat[j][i];
        }
    }
    return mat;
}

// Returns the characteristic polynomial of the specified matrix.
// Requires `mat` to be a square matrix.
// Reference: https://judge.yosupo.jp/problem/characteristic_polynomial
template <compatible_modint mint> std::vector<mint> charpoly(const matrix<mint> &mat) {
    if (mat.empty()) return {1};
    int n = mat.size();
    matrix<mint> hess = upper_hessenberg(mat);
    matrix<mint> poly(n + 1);
    poly[0] = {1};
    poly[1] = {-hess[0][0], 1};
    for (int i = 2; i <= n; i++) {
        poly[i].resize(i + 1);
        for (int j = 0; j < i; j++) poly[i][j] = poly[i - 1][j] * -hess[i - 1][i - 1];
        for (int j = 0; j < i; j++) poly[i][j + 1] += poly[i - 1][j];
        mint acc = 1;
        for (int j = 1; j < i; j++) {
            acc *= hess[i - j][i - j - 1];
            mint prod = acc * hess[i - j - 1][i - 1];
            for (int k = 0; k < i - j; k++) poly[i][k] -= prod * poly[i - j - 1][k];
        }
    }
    return poly[n];
}

}  // namespace matrix

}  // namespace kotone

#endif  // KOTONE_MATRIX_HPP

using mint = atcoder::modint998244353;

std::vector<mint> det(std::vector<std::vector<mint>> m0, std::vector<std::vector<mint>> m1) {
    int n = m0.size(), d = 0;
    mint det = 1;
    for (int k = 0; k < n; k++) {
        while (m1[k][k] == 0) {
            for (int j = k + 1; j < n; j++) {
                if (m1[k][j] == 0) continue;
                for (int i = 0; i < n; i++) std::swap(m0[i][k], m0[i][j]);
                for (int i = 0; i < n; i++) std::swap(m1[i][k], m1[i][j]);
                det = -det;
                break;
            }
            if (m1[k][k] != 0) break;
            if (++d > n) return std::vector<mint>(n + 1);
            std::swap(m0[k], m1[k]);
            for (int i = 0; i < k; i++) {
                mint acc = m1[k][i];
                for (int j = 0; j < n; j++) m0[k][j] -= acc * m0[i][j];
                for (int j = 0; j < n; j++) m1[k][j] -= acc * m1[i][j];
            }
        }
        det *= m1[k][k];
        mint inv = m1[k][k].inv();
        for (mint &m : m0[k]) m *= inv;
        for (mint &m : m1[k]) m *= inv;
        for (int i = 0; i < n; i++) {
            if (i == k) continue;
            mint acc = m1[i][k];
            for (int j = 0; j < n; j++) m0[i][j] -= acc * m0[k][j];
            for (int j = 0; j < n; j++) m1[i][j] -= acc * m1[k][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) m0[i][j] = -m0[i][j];
    }
    std::vector<mint> p = kotone::matrix::charpoly(m0);
    std::vector<mint> result(n + 1);
    for (int i = 0; i + d <= n; i++) result[i] = det * p[i + d];
    return result;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    atcoder::dsu dsu(N);
    std::vector graph(N, std::vector<bool>(N));
    while (M--) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        dsu.merge(u, v);
        graph[u][v] = graph[v][u] = true;
    }

    if (dsu.size(0) == N) {
        std::vector m0(N, std::vector<mint>(N));
        std::vector m1(N, std::vector<mint>(N));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                auto &m = graph[i][j] ? m0 : m1;
                m[i][i]++;
                m[i][j]--;
                m[j][i]--;
                m[j][j]++;
            }
        }
        m0.pop_back();
        for (auto &m : m0) m.pop_back();
        m1.pop_back();
        for (auto &m : m1) m.pop_back();
        std::vector<mint> p = det(m0, m1);
        std::cout << 0 << '\n' << (p[0] + p[1]).val() << std::endl;
        return 0;
    }

    int count = 0;
    mint result = 1;
    int nmax = -1, cmax = 0, nmax2 = -1, cmax2 = 0;
    for (auto &g : dsu.groups()) {
        int n = g.size();
        count += n * (N - n);
        if (n > nmax) nmax2 = nmax, cmax2 = cmax, nmax = n, cmax = 1;
        else if (n == nmax) cmax++;
        else if (n > nmax2) nmax2 = n, cmax2 = 1;
        else if (n == nmax2) cmax2++;
        std::vector mat(n, std::vector<mint>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (!graph[g[i]][g[j]]) continue;
                mat[i][i]++;
                mat[i][j]--;
                mat[j][i]--;
                mat[j][j]++;
            }
        }
        mat.pop_back();
        for (auto &m : mat) m.pop_back();
        result *= kotone::matrix::det(mat);
    }

    if (cmax == 1) {
        count -= nmax * nmax2 * 2;
        result *= nmax * nmax2 * cmax2;
    } else {
        count -= nmax * nmax * 2;
        result *= cmax * (cmax - 1) / 2 * nmax * nmax;
    }
    std::cout << count << '\n' << result.val() << std::endl;
}