[yukicoder] No.1762 🐙🐄🌲

スポンサーリンク

概要

問題文 → ■
公式解説 → ■
自分の提出 → ■

解法

まずは $P$ のことを忘れて解きます.$N=4n+1$ とします.

次の指数型母関数を考えます:

  • $A(x) = \sum \dfrac{a_n}{n!}x^n$,$a_n$ はラベル付き $n$ 頂点を絵付き根付き木にする方法の総数.ただし根は「うし」であり,根の次数は $3$ であり、根以外の頂点は問題の次数制約を満たす
  • $B(x) = \sum \dfrac{b_n}{n!}x^n$,$b_n$ はラベル付き $n$ 頂点を絵付き根付き木にする方法の総数.ただし根は「タコ」であり,根の次数は $7$ 以下であり,根以外の頂点は問題の次数制約を満たす.

$A$ は $B$ を用いて表せます.根に $3$ つの部分木をつけますが,これらの部分木にもラベルをつける場合の数え上げは $\sum_{i+j+k=n-1}b_ib_jb_k\dfrac{n!}{1!a!b!c!} = n![x^n]xB(x)^3$ です.部分木のラベルを忘れて,$a_n = \frac{1}{6}\cdot n![x^n]xB(x)^3$ より $A(x) = \frac16 xB(x)^3$ となります.

同様に $B(x) = x\sum_{k=0}^7 \frac{1}{k!}A(x)^k$ となります.

ここから $A(x)$ が求められそうです.$f(x) = \sum_{k=0}^7\frac{1}{k!}x^k$ としましょう.すると,$A(x) = \frac16 xB(x)^3 = \frac16 x^4 f(A(x))^3$ です.$g(x) = \frac{6x}{f(x)^3}$ に対して $g(A(x))=x^4$ という関係が得られます.

ところで,$A$ の数え上げが $0$ でないとき頂点数は $4$ の倍数でないことが分かります.したがってある $a(x)$ を用いて $A(x)=a(x^4)$ と書けて,この $a$ について $g(a(x))=x$ が分かります.


($P$ の扱いは未だ放置していますが)ひとまず $a(x)$ がラグランジュ反転を用いて扱えそうな格好になりました.次にタコうし木の数え上げについて考えます.$N=4n+1$ 頂点のタコうし木について $n$ 個の「タコ」,$N-n$ 個の「うし」があります.そこで,「根付きタコうし木」であって根がうしであるものの総数を計算し,それを $N-n$ で割ることで答を求めましょう.根の次数 $k$ で場合分けすれば,答は次のようになることが分かります:

$$\frac{1}{N-n}\cdot N!\sum_{k=1}^8[x^{N-1}]A(x)^k = \frac{1}{N-n}\cdot N!\sum_{k=0}^8[x^{n}]a(x)^k.$$

$[x^n]a(x)^k$ をラグランジュ反転で計算すれば,答は

$$\frac{1}{N-n}\cdot N!\sum_{k=1}^8[x^{N-1}]A(x)^k = \frac{N!}{n(N-n)}\sum_{k=1}^8[x^{-1}]kx^{k-1}g(x)^{-n}= \frac{N!}{n(N-n)6^n}\sum_{k=1}^8k[x^{n-k}]f(x)^{3n}.$$

これでタコうし木が数えられました.


ここに「完全なタコ」情報を付加するのは簡単です.完全なタコの個数を表す変数 $y$ をつけて,$2$ 変数母関数を考えます.

$a_k = \begin{cases}1 & (k=7)\\ 0 & (k\neq 7)\end{cases}$, $b_k = \begin{cases}1 & (k=8)\\ 0 & (k\neq 8)\end{cases}$ として,$f(x) = \sum_{k=0}^7 \frac{1}{k!}x^k$ の代わりに $f(x,y)=\sum_{k=0}^7\frac{1}{k!}x^ky^{a_k}$ を考えると,答は次のようになります.

$$\frac{N!}{n(N-n)6^n}\sum_{k=1}^8k[x^{n-k}y^{P-b_k}]f(x,y)^{3n}.$$

結局 $[x^iy^j]f(x,y)^{3n}$ という形の計算を $O(1)$ 回行えばよいことになりますが,$f(x,y)$ は $y$ について $1$ 次なので $f(x,y)=f_0(x)+yf_1(x)$ と表して二項定理を使って $[y^j]$ 部分を取り出せば,$[x^i]f_0(x)^{m}$ の形に計算に帰着されます.疎な形式的べき級数の pow を計算できればよく,計算量 $O(N)$ 時間で解くことができます.

タイトルとURLをコピーしました