\(O(N^22^N)\) 時間で解くことができます。

以下単に集合と言えば、\(\{1,\ldots,n\}\)の部分集合を指すこととします。集合全体を定義域とする関数を集合関数ということにします。他の方の解説にもあるように、本問題は次の計算に帰着できます。

集合関数 \(f\) がある。次によって定まる集合関数 \(g\) を計算せよ：

\[g(s) = \frac{1}{k!}\sum f(t_1)\cdots f(t_k)\]

ただし和は、\(s\) の空でない部分集合への分割 \(s = t_1\amalg\cdots \amalg t_k\)（順序対）をわたる。

\(f, g\) を集合関数とするとき、subset convolution \(f\star g\) を次のように定義します。

\[f\star g(s) = \sum_{t\subset s} f(t)g(s\setminus t).\]

これは、\(f\) に集合の要素数という情報を付加した上で、bitwise-or convolution を行うことで \(O(N^22^N)\) 時間で計算できます。つまり、部分集合ゼータ・メビウス変換により多項式の各点積に変換することで高速に計算できます。

• 参考：https://judge.yosupo.jp/problem/subset_convolution

さて、subset convolution を用いると、本問題で計算したいものは

\[\exp f = \sum_{k}\frac{1}{k!} \underbrace{f\star\cdots\star f}_{k}\]

です。これも subset convolution と同じ要領で計算できます。多項式の各点積の代わりに、各点で形式的べき級数の \(\exp\) をとればよいです。

今回は \(\exp f\) 全体は不要で、全体集合における値のみ必要なので、メビウス変換の代わりに包除原理を使うことで定数倍高速化が可能です。

• 解答例：https://atcoder.jp/contests/abc236/submissions/31394125