Sadly, I cannot get the motivation to transform dp into dp2 in the official editorial. Here’s a more natural (and knowledge oriented) formulation.

Suppose that we want to compute

\[W_k = \left( \sum_{1 \leqslant i_0 < \ldots < i_{k - 1} < n} \prod_{j = 0}^{k - 1} (\textrm{count} [i_j] - j) \right) \]

, which can be understood as “the number of way to place \(k\) rooks on a Ferre Board \((\mathrm{count}[0], \dots, \mathrm{count}[n - 1])\)”.

Using Rook Factorization Theorem, we have

\[ \sum_{k = 0}^n W_{n - k} z^{\underline{k}} = \prod_{i = 0}^{n - 1} (z + \textrm{count} [i] - i) \]

and the r.h.s. can be multiplied out in \(O(n \log^2 n)\) time. What left is to convert a polynomial to the left hand size.

We should have

\[ \begin{aligned} & \left[ z^{\underline{j}} \right] \sum_{i = 0}^n a_i z^i\\ = & \sum_{i = 0}^n S(i, j) a_i\\ = & \sum_{i = 0}^n \frac{\sum_{k = 0}^j (- 1)^{j - k} \binom{j}{k} k^i}{j!} a_i\\ = & \sum_{i = 0}^n \left( \sum_{k = 0}^j \frac{(- 1)^{j - k} k^i}{k! (j - k) !} \right) a_i .\\ = & \sum_{i = 0}^n \left( [t^j] \left( \sum_{k = 0}^n \frac{k^i}{k!} t^k \right) \left( \sum_{k = 0}^n \frac{(- 1)^k}{k!} t^k \right) \right) a_i\\ = & [t^j] \left( \sum_{k = 0}^n \frac{A (k)}{k!} t^k \right) \left( \sum_{k = 0}^n \frac{(- 1)^k}{k!} t^k \right)\\ = & [t^j] \left( \sum_{k = 0}^n \frac{A (k)}{k!} t^k \right) e^{- t} \end{aligned} \]

where\(A (k) = \sum_{i = 0}^n a_i k^i\) can be computed with multi-eval.