「FPS 24 題」全部解く: M「連結グラフ」

解きます

解く

連結じゃないグラフはより小さい連結なグラフの組み合わせなので, 連結じゃないグラフを数えて全体から引く方針が良さそうですね.

まず, 連結かは問わず, $n$頂点の単純無向グラフは$2^{n\left(n-1\right)/2}$個あります. 頂点のペアごとに辺のある/なしを決める感じです.

$a_n$を$n$頂点の単純連結無向グラフの個数とします. 結論から言うと$a_n$は
$$n!\left[x^n\right]\exp\sum_{i=1}^n\frac{a_ix^i}{i!} = 2^{n\left(n-1\right)/2}$$
を満たします. まず, $n$頂点の連結か問わない単純無向グラフの個数を$b_n$と書くことにして, 例えば同じ頂点数の連結成分が高々1つしかないと制限を付けた場合, 式は
$$b_n'=n!\left[x^n\right]\prod_{i=1}^n1+\frac{a_ix^i}{i!}$$
となります. 高々2つにすると,
$$b_n'=n!\left[x^n\right]\prod_{i=1}^n1+a_ix^i+\frac{a_i^2x^{2i}}{2\left(i!\right)}$$
こうなります. 分母の$2$は同じ頂点数の連結成分が2つあった場合にそれらを入れ換えたものを同一視するためです.
このノリで連結成分数の上限を無くすと
$$\begin{align}
b_n=n!\left[x^n\right]\prod_{i=1}^n1+a_ix^i+\frac{a_i^2x^{2i}}{\left(2!\right)\left(i!\right)}+\frac{a_i^3x^{3i}}{\left(3!\right)\left(i!\right)}+\cdots \\
=n!\left[x^n\right]\prod_{i=1}^n\exp\frac{a_ix^i}{i!} \\
=n!\left[x^n\right]\exp\sum_{i=1}^n\frac{a_ix^i}{i!} \\
\end{align}$$
このようになります. 最初に書いた通り$b_n=2^{n(n-1)/2}$なので
$$n!\left[x^n\right]\exp\sum_{i=1}^n\frac{a_ix^i}{i!} = 2^{n\left(n-1\right)/2}$$
という訳です.
さて, 明らかに指数型母関数にしたい形をしているので, $f=\sum_{k=0}^\infty a_nx^n/n!$として
$$\begin{align}
\exp f &= \sum_{k=0}^\infty\frac{2^{k\left(k-1\right)/2}}{k!}x^k \\
f &= \log\sum_{k=0}^\infty\frac{2^{k\left(k-1\right)/2}}{k!}x^k
\end{align}$$
$\log$が計算できたら終わりです. これは$\log g = \int\frac{g'}g\mathrm dx$という風に求められます. 置換積分ですね.

use ac_library::*;
use proconio::*;

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
    }
    // 階乗テーブル
    let factorial = {
        let mut r = vec![Mint::raw(1)];
        for i in 1..262144 {
            r.push(r[i - 1] * i);
        }
        r
    };

    // 対数の中身
    let h = (0..(n + 1).next_power_of_two())
        .map(|k| {
            if k == 0 {
                Mint::raw(1)
            } else {
                Mint::raw(2).pow((k * (k - 1) / 2) as u64) / factorial[k]
            }
        })
        .collect::<Vec<_>>();

    // 1/h. ニュートン法で求める
    let mut hr = vec![Mint::raw(1)];
    while hr.len() < h.len() {
        let m = convolution(&hr, &hr);
        let m = convolution(&m, &h[..hr.len() * 2]);
        hr.extend((0..hr.len()).map(|_| Mint::raw(0)));
        for i in 0..hr.len() {
            hr[i] = hr[i] * 2 - m[i];
        }
    }
    // h'
    let hd = h
        .iter()
        .enumerate()
        .skip(1)
        .map(|(i, &v)| v * i)
        .collect::<Vec<_>>();
    // h'/h
    let g = convolution(&hr, &hd);
    // [x^n]f
    let ans = g[n - 1] / n;
    // 指数型母関数なのでn!をかける
    println!("{}", ans * factorial[n]);
}

提出(209 ms):

終わり

考察して答え合わないなーと思ってたら最初の方で壮大にミスして書き直しになりました
以上です