\(A \leq |S_i| \leq B\) なる分割の個数

全体の個数が \(n\) のときの個数を \(B_n\) と置くと、漸化式 \(B_{n+1}=\sum_{k=A-1}^{B-1} \binom{n}{k} B_{n-k}\) が成り立ちます。

\(g=\sum_n B_n {x^n \over n!}\) と置くと上の式は \(g=\exp(\sum_{k=A}^{B} {x^k \over k!})\) と書き直せるので、FPS expを用いて \(O(N \log N)\) で列挙できます。

\(A \leq |S_i| \leq B\) かつ良い分割の個数

\(S_i\) 内の要素は全て連結になるので、異なる部分集合に入るペアの連結性を考えます。

\(S_i,S_j\ (i \neq j)\) の要素 \(a,b \in S_i\) と \(c,d \in S_j\) で \(a<c<b<d\) なる組が存在したとき、どのような \(\{H_i\}\) についても両者は連結になります。逆に、このような組が存在するという二項関係に推移性を追加したもので \(S_i\) と \(S_j\) が結ばれない時、連結にならないよう \(\{H_i\}\) を設定することが出来ます。

全体の個数が \(n\) のときの \(A \leq |S_i| \leq B\) かつ良い分割の個数を \(C_n\) 、\(f=\sum_n C_n {x^n \over n!}\) と置きます。

\(B_n\) の元を一つ取り左端を含む連結成分を \(\{a_1=1,a_2,\ldots,a_k\}\) とすると \((a_1,a_2),\ldots,(a_{k-1},a_k),(a_k,n]\) の範囲が部分分割をなしていることが分かります。よって、漸化式

\[B_n= \sum_{k \leq n} C_k \sum_{i_1+\cdots+i_k=n-k} B_{i_1}\cdots B_{i_k}= \sum_{k \leq n} C_k [x^{n-k}]g^k\]

より \(g=f \circ (xg)\) を得ます。\(O(N \log^2 N)\) のFPS合成・合成invを用いて \(f\) を直接計算することもできますが、Lagrange反転によってFPS inv,powのみの \(O(N \log N)\) で計算することも可能です。

Bonus: 図の連結成分サイズの最小値が \(C\) であるような分割の個数を \(O(NC \log^2 (NC))\) で数え上げることができます。