一半看到这种代价为 \(k\) 次方的形式，且需要转移复杂度的题，都是用第二类斯特林数解决的
第二类斯特林数我们记作 \(\begin{Bmatrix} n \\\\ m \end{Bmatrix}\) 表示将 \(n\) 个相互作区分的元素放入 \(m\) 个不做区分的集合里，每个集合元素非空的方案数，我们很容易就能有多项式得到一个恒等式
我们不妨计 \(\begin{Bmatrix} n \\\\ m
\end{Bmatrix}\times m!\) 的 egf 为 \(f\)，即集合做区分的母函数，考虑另一个
egf 为 \(g_n\) 满足
\[ g_n=\sum_{i}i^n\frac{x^i}{i!} \] 很显然 \([x^m]g_n\) 的意义就是我们要求做区分的集合可以为空的方案数的生成函数，那么显然有
\[ e^xf=g_n \]
我们就可以得到
\[ m^n=\sum_{i=0}^{\min(n,m)}\binom{m}{i}\begin{Bmatrix} n \\\\ i \end{Bmatrix}\times i! \]
所以代入这道题要求的式子
\[ \sum_{\sum_{i=1}^mx_i=n}\prod_{i=1}^mx_i^{k_i} \]
化简得到
\[ \sum_{\sum_{i=1}^mx_i=n}\prod_{i=1}^m\sum_{j=0}^{\min(x_i,k_i)}\binom{x_i}{j}\begin{Bmatrix} k_i \\\\ j \end{Bmatrix}\times j! \]
注意到 \(\sum_{i=1}^mk_i\le1\times10^5\)，所以我们考虑求这样的多项式
\[ \sum_{\sum_{i=1}^mx_i=n}\prod_{i=1}^m\sum_{j=0}^{\min(x_i,k_i)}\binom{x_i}{j}\begin{Bmatrix} k_i \\\\ j \end{Bmatrix}\times j!\ x^j \]
那么我们就可以将最内侧的和式移到外面
\[ \sum_j\sum_{\sum_{i=1}^mc_i=j}\sum_{\sum_{i=1}^mx_i=n}\prod_{i=1}^m\binom{x_i}{c_i}\prod_{i=1}^m\begin{Bmatrix} k_i \\\\ c_i \end{Bmatrix}\times c_i!\ x^j \]
我们注意到中间的
\[ \sum_{\sum_{i=1}^mx_i=n}\prod_{i=1}^m\binom{x_i}{c_i} \]
实际上是有组合意义的，与隔板法非常类似，我们想象有个长度为 \(n+m-1\) 的序列，我们从中选出 \(m-1+\sum_{i=1}^mc_i\) 个元素，对于每一种选择方案我们这样构造，先是 \(c_1\) 个元素，再算上 \(1\) 个隔板依次类推，所以答案的多项式又可以简化为
\[ \sum_j\sum_{\sum_{i=1}^mc_i=j}\binom{n+m-1}{m-1+j}\prod_{i=1}^m\begin{Bmatrix} k_i \\\\ c_i \end{Bmatrix}\times c_i!\ x^j \]
而实际上我们只需要多项式
\[ \prod_{i=1}^m\sum_{j=0}^{k_i}\begin{Bmatrix} k_i \\\\ j \end{Bmatrix}\times j!\ x^j \]
再算上相应的系数即可
那么用最开始斯特林数的生成函数的等式
那么为
\[ \prod_{i=1}^m\sum_{j=0}^{k_i}j!\times[x^j]{(}e^{-x}\times g_{k_i}{)}\ x^j \]
实际上后面的 \(e^x\) 和 \(g_{k_i}\) 只需要求到 \(x^{k_i}\) 即可，那么整个式子可以用分治
FFT 优化，用一个类似于线段树的结构求出
\[ \prod_{i=l}^r\sum_{j=0}^{k_i}j!\times[x^j]{(}e^{-x}\times g_{k_i}{)}\ x^j \]
每一层总的项数和为 \(S=\sum_{i=1}^mk_i\) 所以复杂度为 \(\operatorname{O}(S\log^2S)\)
其他类似题目可参照 [BZOJ 5093] 图的价值
1 |
|