ABC321 G - Electric Circuit

最終更新: 2026-05-16

問題へのリンク

問題概要

$N$ 頂点 $0$ 辺の無向グラフと長さ $M$ の数列 $R, B$ が与えられる。

$B$ のすべての並び替えに対して頂点 $R_i$ と頂点 $B_i$ を辺で結んだとき、連結成分の個数の期待値を求めよ。

・$N \le 17$

・$M \le 10^5$

600点

解説

$S = \{1, 2, \dots, N\}$ とする。

連結成分の個数の期待値は、

$f(T) = グラフ内のTに含まれる任意の頂点と連結な頂点集合が T と一致する B の並び替えの個数$

とすることで $\dfrac{1}{M!}\displaystyle\sum_{T\subseteq S}f(T)$ と表せる。

$f(T)$ について考える。 $|T| = 3$ のとき、 $T$ の $1$ つ以上の集合の分割は以下の $5$ 通りがある。

色を入れ替えても影響はないので、左側(頂点番号の最小値)が常に赤になるように入れ替えることができる。

赤色の点が表す部分集合について考えると、

$g(T) = グラフ内のTに含まれる任意の頂点と連結な頂点集合が T に含まれる B の並び替えの個数$ とすることで、 $f(T) = g(T) - \displaystyle\sum_{U\subset T, \min(S) \in U} f(U)g(T\backslash U)$

この式を昇順にdp を適用して計算することで $f(T)$ を決定することができる。

$g(T) = \left(\displaystyle\sum_{i \in T}r_i\right)!$ であるので、

計算量は $\displaystyle\sum_{0 \le i \le N} \dbinom{N}{i}2^i = 3^N$ であるので $O(3^N)$ である。

実装上の注意

$\displaystyle\sum_{i \in T}r_i = \displaystyle\sum_{i \in T}b_i$ であるとき、辺の入次数と出次数が一致しないため、条件を満たす繋ぎ方が存在しないことに注意。

AC コード

提出へのリンク

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for (ll i=0; i<(ll)(n); i++)
const ll mod = 998244353;
const int inf = numeric_limits<int>::max()/2;
const ll INF = numeric_limits<ll>::max()/2;

#include <atcoder/modint>
using mint = atcoder::modint998244353;

void solve() {
    int n, m; cin >> n >> m;
    vector<int> r(n), b(n);
    rep(i, m) {
        int x; cin >> x; x--;
        r[x]++;
    }
    rep(i, m) {
        int x; cin >> x; x--;
        b[x]++;
    }
    vector<mint> fact(m+1, 1); rep(i, m) fact[i+1] = fact[i] * (i + 1);
    vector<mint> f(1<<n), g(1<<n);
    mint ans=0;
    for (int i=1; i<(1<<n); i++) {
        int sr=0, sb=0;
        rep(j, n) if ((i>>j)&1) { sr += r[j]; sb += b[j]; }
        if (sr != sb) continue;
        f[i] = g[i] = fact[sr];
        for (int j=(i-1)&i; j; j=(j-1)&i) {
            if (i < (j<<1)) {
                f[i] -= f[j] * g[i^j];
            }
        }
        ans += f[i] * fact[m-sr];
    }
    cout << (ans / fact[m]).val() << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}