公式解説とは若干式変形の異なる解法です．

包除原理より次が成り立ちます．

• \((\)求める値\()=(\)入力の総数\()-(\)Alice が AC となる入力の個数\()-(\)Bob が AC となる入力の個数\()+(\)Alice, Bob 共に AC となる入力の個数\()\)

Alice が AC となる入力のうち，作られるグラフでサイズ \(n\) のサイクルが \(C_n\) 個あるものの個数は次のようになります． \[ \left(\frac{N!}{\prod_{n\geq 1}(n!)^{C_n}}\right) \left(\prod_{n\geq 1}\frac{1}{C_n!}\right) \left(\prod_{n\geq 1}\bigl((n-1)!\bigr)^{C_n}\right) \left(\frac{N!}{\prod_{n\geq 1}n^{C_n}}\right)\]

• 1つ目の大括弧：多項係数．
• 2つ目の大括弧：同じサイズのサイクルの順序は区別しないため．
• 3つ目の大括弧：サイクル内での頂点の並べ方（円順列）．
• 4つ目の大括弧：\(Q\) の決め方（各サイクルにおいて，頂点番号が最小の頂点から出る辺の重さがそのサイクル内で最小）．

整理すれば \[(N!)^2\prod_{n\geq 1}\frac{1}{C_n!\cdot n^{2C_n}}\] となります． これを \(\sum_{n\geq 1}nC_n=N\) となる非負整数列 \((C_1,C_2,\dots)\) 全てについて足し合わせたものは，形式的冪級数を用い次のように表せます．

\[(N!)^2[x^N]\prod_{n=1}^{N}\left(\sum_{k\geq 0}\frac{1}{k!n^{2k}}x^{nk}\right)\]

ここで \[\sum_{k\geq 0}\frac{1}{k!n^{2k}}x^{nk} =\sum_{k\geq 0}\frac{1}{k!}\left(\frac{x^n}{n^2}\right)^k =\exp\left(\frac{x^n}{n^2}\right)\]

です． また通常の指数関数と同様に，\([x^0]f=[x^0]g=0\) となる形式的冪級数 \(f,g\) について \(\exp(f)\exp(g)=\exp(f+g)\) が成り立ちます（参考：maspyのHP, [多項式・形式的べき級数] （補足）定義や式変形の正当性の確認）．従って，結局 Alice が AC となる入力の個数は

\[(N!)^2[x^N]\prod_{n=1}^{N}\exp\left(\frac{x^n}{n^2}\right) =(N!)^2[x^N]\exp\left(\sum_{n=1}^{N}\frac{x^n}{n^2}\right)\]

個です．

Bob が AC となる入力の個数も同じです．またAlice,Bob 共に AC となるのは全てのサイクルがサイズ \(1\) である場合で，\(N!\) ケース存在します．

以上を合わせれば求める値は \[(N!)^2\left(1-2[x^N]\exp\left(\sum_{n=1}^{N}\frac{x^n}{n^2}\right)\right)+N!\]

となり，公式解説と同じ式が得られました．