loj6728 U 群把妹王
The most important part is the PIE coefficient.
with out loss of generality, consider the case of 1 dimension.
denote \(p:n\) \(p\in\) partitions of the set \([n]\), \(|p_i|\) the size of the i-th part and \(|p:n|\) the number of parts.
\(f(n)\) the fake answer(with something counted more than once). \(g(n)\) the genuine answer. \(d(n)\) the answer that all the part are distinct.
\(c(n)\) the PIE coefficient.
\[f(n)=\sum_id(i)\sum[|p:n|=i]
\]
\[g(n)=\sum_id(i)\sum_{|p:n|=i}\prod_j[|p_j|\in S]
\]
if we choose \(c(n)\) that satisfy
\[\sum_{p:n}(\prod_j c(|p_j|))=[n\in S]
\]
simplify \(g(n)\)
\[g(n)=\sum_id(i)\sum_{|p:n|=i}\prod_j\sum_{q:|p_j|}\prod_kc(|q_k|)
\]
\[=\sum_id(i)\sum_{q:n}\begin{Bmatrix}|q:n|\\i \end{Bmatrix}\prod_kc(|q_k|)
\]
\[=\sum_j\sum_{|q:n|=j}\prod_kc(q_k)\sum_i \begin{Bmatrix}j\\i \end{Bmatrix}d(i)
\]
\[=\sum_j\sum_{|q:n|=j}\prod_kc(q_k)f(j)
\]
this is equivalent to first get \(c\) by
\[\exp(\sum_k\frac{c(k)x^k}{k!})=1+\sum_{k\in S}\frac{x^k}{k!}
\]
then calculate
\[\sum_jf(j)(\sum_k\frac{c(k)x^k}{k!})^j\frac{1}{j!}[x^n]n!
\]