先考虑一下朴素的 dp。

不难发现，对于一个集合最重要的是集合里最小的元素，剩下的元素对应的 $a_i$ 都大于这个值，可以考虑把所有值按照从大到小排序，则集合里其他元素都在最小元素之前。

对于第 $i$ 个数，考虑这个数是集合里最小的元素，或不是最小的元素对应的方案数。 $dp_{i,j}$ 表示 $1\sim i-1$ 个数处理完后，还剩下 $j$ 个数未确定属于哪个集合的方案数。

若第 $i$ 个数不是集合里最小的元素：

$$dp_{i+1,j+1}\gets dp_{i,j}$$

若第 $i$ 个数是集合里最小的元素，枚举这个集合里还有几个元素，即：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \text{C}_j^k(0\le k<a_i)$$

初始状态为 $dp_{1,0}=dp_{1,1}=1$，目标状态为 $dp_{n+1,0}$。转移的过程中对于第二类转移需要枚举 $k$，复杂度为 $O(n^3)$。

考虑如何优化这个 dp 的第二类转移，将组合数拆开得到：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \frac{j!}{k!(j-k)!}$$

假定对于阶段 $i$，设有

$$F(x)=\sum_{i>0}dp_{i,j}j!x^j$$

$$G(x)=\sum_{i>0}\frac{1}{k!}$$

实际上是将 $F,G$ 做一个减法卷积的到 $H$，则有

$$H(x)=\sum_{i>0}dp_{i+1,j}j!x^j$$

对于减法卷积，可以翻转一个多项式的次数，此时减法卷积就转化成了加法卷积，直接用 NTT 计算即可。

可以选择为 $dp_{i,j}$，也可以直接维护 $dp_{i,j}\times j!$。算法的复杂度为 $O(n^2\log n)$。