#1193806 (C++23) No.2507 Yet Another Subgraph Counting

• 問題: No.2507 Yet Another Subgraph Counting
• ユーザー: akakimidori
• 提出日時: 2026-10-20 08:17:21
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 11,987 bytes
• コンパイル時間: 2,268 ms
• コンパイル使用メモリ: 245,908 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-10-20 08:17:32
• 合計ジャッジ時間: 5,656 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
other	AC * 52

ソースコード

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <vector>
#include <numeric>
#include <span>
#include <ranges>

namespace mylib {

constexpr uint32_t calc_rem_expr(uint32_t m) {
    uint32_t t = 1;
    uint32_t s = ~m + 1;
    uint32_t n = ~(uint32_t)0 >> 2;
    while (n) {
        if (n & 1) t *= s;
        s *= s;
        n >>= 1;
    }
    return t;
}

template <uint32_t M>
class modint {
public:
    constexpr static uint32_t mod() { return M; }
    modint() : v_(0) {}
    template <class T>
    requires std::unsigned_integral<T>
    constexpr modint(T v) {
        v_ = raw(v % mod());
    }
    template <class T>
    requires std::signed_integral<T>
    constexpr modint(T v) {
        int64_t u = v % (int64_t)mod();
        if (u < 0) u += mod();
        v_ = raw(static_cast<uint32_t>(u));
    }
    constexpr uint32_t val() const {
        const uint32_t res = reduce(v_);
        return res >= mod() ? res - mod() : res;
    }
    constexpr modint &operator+=(const modint &rhs) {
        v_ += rhs.v_;
        v_ -= v_ >= 2 * mod() ? 2 * mod() : 0;
        return *this;
    }
    constexpr modint &operator-=(const modint &rhs) {
        v_ = v_ - rhs.v_ + (v_ < rhs.v_ ? 2 * mod() : 0);
        return *this;
    }
    constexpr modint &operator*=(const modint &rhs) {
        v_ = reduce((uint64_t)v_ * rhs.v_);
        return *this;
    }
    constexpr modint &operator/=(const modint &rhs) { return *this *= rhs.inv(); }
    template <class T>
    requires std::integral<T>
    constexpr modint pow(T n) const {
        assert(n >= 0);
        modint t = 1;
        modint r = *this;
        while (n) {
            if (n & 1) t *= r;
            r *= r;
            n >>= 1;
        }
        return t;
    }
    constexpr modint inv() const {
        assert(v_ > 0);
        return pow(mod() - 2);
    }
    friend constexpr modint operator+(const modint &lhs, const modint &rhs) {
        return modint(lhs) += rhs;
    }
    friend constexpr modint operator-(const modint &lhs, const modint &rhs) {
        return modint(lhs) -= rhs;
    }
    friend constexpr modint operator*(const modint &lhs, const modint &rhs) {
        return modint(lhs) *= rhs;
    }
    friend constexpr modint operator/(const modint &lhs, const modint &rhs) {
        return modint(lhs) /= rhs;
    }
    constexpr modint operator+() const {
        return *this;
    }
    constexpr modint operator-() const {
        modint res;
        res.v_ = v_ == 0 ? 0 : 2 * mod() - v_;
        return res;
    }
    constexpr bool operator==(const modint &rhs) const {
        return (v_ >= mod() ? v_ - mod() : v_) == (rhs.v_ >= mod() ? rhs.v_ - mod() : rhs.v_);
    }
private:
    uint32_t v_;
    constexpr static uint32_t rem = calc_rem_expr(M);
    constexpr static uint64_t ini = ((((uint64_t)1 << 32) % mod()) << 32) % mod();
    constexpr static uint32_t reduce(const uint64_t x) {
        return (x + (uint32_t)x * rem * (uint64_t)mod()) >> 32;
    }
    constexpr static uint32_t raw(uint32_t v) { return reduce(v * ini); }
    static_assert(mod() < (1 << 30));
    static_assert((mod() & 1) == 1);
};

template <typename T>
class Binomial {
public:
    Binomial(const int n) : n_(n) {
        assert(n >= 0);
        fact_.resize(n + 1, T(1));
        ifact_.resize(n + 1, T(1));
        inv_.resize(n + 1, T(1));
        for (const int i : std::views::iota(1, n + 1)) fact_[i] = i * fact_[i - 1];
        ifact_[n] = 1 / fact_[n];
        for (const int i : std::views::iota(0, n) | std::views::reverse) {
            ifact_[i] = ifact_[i + 1] * (i + 1);
            inv_[i + 1] = ifact_[i + 1] * fact_[i];
        }
    }
    T fact(int n) {
        assert(n <= n_);
        return fact_[n];
    }
    T ifact(int n) {
        assert(n <= n_);
        return ifact_[n];
    }
    T binom(int n, int k) {
        if (k < 0 || n < k) return 0;
        assert(n <= n_);
        return fact(n) * ifact(n - k) * ifact(k);
    }
    T inv(int n) {
        assert(0 < n && n <= n_);
        return inv_[n];
    }
private:
    const int n_;
    std::vector<T> fact_, ifact_, inv_;
};

}    // namespace mylib

namespace sps {

template <typename T>
std::vector<T> conv(std::span<const T> a, std::span<const T> b) {
    std::size_t len = a.size(), n = std::countr_zero(len);
    assert(len > 0 && len == (1ul << n) && len == b.size());
    std::vector<T> x((n + 1) << n, T(0)), y((n + 1) << n, T(0));
    for (std::size_t i : std::views::iota(0ul, len)) {
        const std::size_t cnt = std::popcount(i);
        x[i * (n + 1) + cnt] = a[i];
        y[i * (n + 1) + cnt] = b[i];
    }
    for (std::size_t i : std::views::iota(0ul, len)) {
        std::size_t s = (n + 1) * i, t = (n + 1) * (i + 1), z = std::countr_zero(i | (1 << n));
        for (std::size_t j : std::views::iota(0ul, z) | std::views::reverse) {
            std::size_t w = (n + 1) << j;
            for (std::size_t k : std::views::iota(0ul, w)) {
                x[s + w + k] += x[s + k];
                y[s + w + k] += y[s + k];
            }
        }
        std::size_t cnt = std::popcount(i);
        for (std::size_t j : std::views::iota(cnt, std::min(n, 2 * cnt) + 1) | std::views::reverse) {
            T v = 0;
            for (std::size_t k : std::views::iota(j - cnt, cnt + 1)) v += x[s + k] * y[s + j - k];
            x[s + j] = v;
        }
        std::size_t o = std::countr_one(i);
        for (std::size_t j : std::views::iota(0ul, o)) {
            std::size_t w = (n + 1) << j, s = t - 2 * w;
            for (std::size_t k : std::views::iota(0ul, w)) x[s + w + k] -= x[s + k];
        }
    }
    std::vector<T> c(1 << n);
    for (std::size_t i : std::views::iota(0ul, len)) c[i] = x[i * (n + 1) + std::popcount(i)];
    return c;
}

// a * b = c なるbを返す a[0] = 1 要求
template <typename T>
std::vector<T> conv_inv(std::span<const T> a, std::span<const T> c) {
    std::size_t len = a.size(), n = std::countr_zero(len);
    assert(len > 0 && len == (1ul << n) && len == c.size() && a[0] == 1);
    std::vector<T> x((n + 1) << n, T(0)), y((n + 1) << n, T(0));
    for (std::size_t i : std::views::iota(0ul, len)) {
        std::size_t cnt = std::popcount(i);
        x[i * (n + 1) + cnt] = a[i];
        y[i * (n + 1) + cnt] = c[i];
    }
    for (std::size_t i : std::views::iota(0ul, len)) {
        std::size_t s = (n + 1) * i, t = (n + 1) * (i + 1), z = std::countr_zero(i | (1 << n));
        for (std::size_t j : std::views::iota(0ul, z) | std::views::reverse) {
            std::size_t w = (n + 1) << j;
            for (std::size_t k : std::views::iota(0ul, w)) {
                x[s + w + k] += x[s + k];
                y[s + w + k] += y[s + k];
            }
        }
        const std::size_t cnt = std::popcount(i);
        for (std::size_t j : std::views::iota(0ul, n + 1)) {
            const T v = y[s + j];
            for (std::size_t k : std::views::iota(1ul, std::min(n - j, cnt) + 1)) y[s + j + k] -= v * x[s + k];
        }
        std::size_t o = std::countr_one(i);
        for (std::size_t j : std::views::iota(0ul, o)) {
            std::size_t w = (n + 1) << j, s = t - 2 * w;
            for (std::size_t k : std::views::iota(0ul, w)) y[s + w + k] -= y[s + k];
        }
    }
    std::vector<T> b(1 << n);
    for (std::size_t i : std::views::iota(0ul, len)) b[i] = y[i * (n + 1) + std::popcount(i)];
    return b;
}

template <class T>
std::vector<T> exp(std::span<const T> a) {
    std::size_t len = a.size(), n = std::countr_zero(len);
    assert(len > 0 && len == (1ul << n) && a[0] == T(0));
    std::vector<T> res(len, T(1));
    for (std::size_t i : std::views::iota(0ul, n)) {
        const auto c = conv<T>(std::span{res}.subspan(0, 1 << i), a.subspan(1 << i, 1 << i));
        std::ranges::copy(c, res.begin() + (1 << i));
    }
    return res;
}

template <class T>
std::vector<T> log(std::span<const T> a) {
    std::size_t len = a.size(), n = std::countr_zero(len);
    assert(len > 0 && len == (1ul << n) && a[0] == T(1));
    std::vector<T> res(len, T(0));
    for (std::size_t i : std::views::iota(0ul, n)) {
        const auto c = conv_inv<T>(a.subspan(0, 1 << i), a.subspan(1 << i, 1 << i));
        std::ranges::copy(c, res.begin() + (1 << i));
    }
    return res;
}

// f: 多項式
// g: sps
template <typename T>
std::vector<T> composite(std::span<const T> f, std::span<const T> g) {
    std::size_t len = g.size(), n = std::countr_zero(len);
    assert(len > 0 && len == (1ul << n));
    std::vector<T> t(f.begin(), f.end());
    std::vector<std::vector<T>> dp(n + 1, {T(0)});
    for (auto &d : dp) {
        if (t.empty()) break;
        for (const auto &v : t | std::views::reverse) d[0] = d[0] * g[0] + v;
        for (std::size_t i : std::views::iota(1ul, t.size())) t[i - 1] = T(i) * t[i];
        t.pop_back();
    }
    for (std::size_t i : std::views::iota(0ul, n)) {
        for (std::size_t j : std::views::iota(1ul, dp.size())) {
            const auto h = conv<T>(g.subspan(1 << i, 1 << i), dp[j]);
            std::ranges::copy(h, std::back_inserter(dp[j - 1]));
        }
        dp.pop_back();
    }
    return dp[0];
}

}    // namespace sps

template <class T, class F>
void bitwise_transform(std::vector<T> &a, F f) {
    const std::size_t len = a.size();
    const int n = std::countr_zero(len);
    assert(len > 0 && len == (1ul << n));
    for (int i = 0; i < n; ++i) {
        const int w = 1 << i;
        for (int j = 0; j < (1 << n); j += 2 * w) {
            for (int k = 0; k < w; ++k) {
                f(a[j + k], a[j + k + w]);
            }
        }
    }
}

using mint = mylib::modint<998244353>;

using i64 = int64_t;
using i32 = int32_t;
using u64 = uint64_t;
using u32 = uint32_t;

template <typename T>
T read() {
    T v;
    std::cin >> v;
    return v;
}

template <class T>
std::vector<T> vec(T elem, int len) {
    return std::vector<T>(len, elem);
}

void yuki2507() {
    const auto n = read<i32>();
    const auto m = read<i32>();
    std::vector<int> g(n, 0);
    for (i32 _ : std::views::iota(0, m)) {
        const auto a = read<i32>() - 1;
        const auto b = read<i32>() - 1;
        g[a] |= 1 << b;
        g[b] |= 1 << a;
    }
    std::vector<u64> dp(1 << n, 0);
    for (const i32 r : std::views::iota(0, n)) {
        auto ep = vec(vec(u64(0), 1 << r), r);
        dp[1 << r] = 2;
        for (const i32 v : std::views::iota(0, r)) if ((g[r] >> v) & 1) ep[v][1 << v] = 1;
        for (const i32 bit : std::views::iota(1, 1 << r)) {
            for (const i32 v : std::views::iota(0, r)) {
                const auto w = ep[v][bit];
                if (w == 0) continue;
                const auto mask = ~bit & g[v];
                for (const i32 u : std::views::iota(0, r)) if ((mask >> u) & 1) ep[u][bit | (1 << u)] += w;
                if (std::popcount((u32)bit) > 1 && ((g[r] >> v) & 1)) {
                    dp[bit | (1 << r)] += w;
                }
            }
        }
    }
    for (auto &v : dp) v /= 2;
    for (const i32 r : std::views::iota(1, n) | std::views::reverse) {
        std::vector<std::vector<u64>> p(2);
        for (const auto [i, v] : dp | std::views::enumerate) {
            p[(i >> r) & 1].emplace_back(v);
        }
        const i32 mask = (1 << r) - 1;
        for (auto [i, p] : p[0] | std::views::enumerate) {
            p *= std::popcount(u32(mask & g[r] & i));
        }
        const auto res = sps::conv<u64>(p[1], sps::exp<u64>(p[0]));
        auto a = dp | std::views::chunk(2 << r);
        auto b = res | std::views::chunk(1 << r);
        for (auto [x, y] : std::views::zip(a, b)) {
            std::ranges::copy(y, x.begin() + (1 << r));
        }
    }
    std::cout << sps::exp<u64>(dp)[(1 << n) - 1] << std::endl;
}

int main(void) {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    yuki2507();
    return 0;
}