题解：P12416 多项式高手

什么叫「转化到拆分 $m$ 为若干不超过 $n$ 的正整数」？
什么叫「显然要将 $a$ 做差分」？
「Ferrers 图辅助理解」怎么理解？
为什么一个人发呆？
谁是多项式高手？

好吧不魔怔了。
很多分拆数的问题都可以用 q-analog 的方法推导，与组合意义解法殊途同归——本题亦不例外。

直接考虑 $b_k$ 这一项对答案产生的贡献，设其为 $g_k$，则：

$g_k = [x^m]\sum_{i \geq 0} i x^i \left( [y^{k-1}]\prod_{j=0}^i \frac{1}{1-y x^j}\right)\left( [y^{n-k}] \prod_{j=i}^\infty \frac{1}{1-y x^j}\right)$ 则答案为 $\sum_k b_k g_k$。

这个 GF 的意义为：枚举第 $k$ 项位置的值，计算此时的序列 $a$ 有多少种 —— 前 $k-1$ 个位置都不大于 $i$，而后 $n-k$ 个位置都不小于 $i$。

利用 q-analog 的推导，我们设

$P(x,y)=\prod_{j=0}^i \frac{1}{1-y x^j}$ 做换元 $y \mapsto xy$，则有 $P(x,xy)=P(x,y) \frac{1-y}{1-y x^{i+1}}$ 在等式两端同乘 $(1-y x^{i+1})$ 并提取 $[y^k]$ 系数得到 $\begin{aligned}x^k p_k-x^{i+k}p_{k-1} &=p_k-p_{k-1} \\ p_k&= \frac{1-x^{i+k}}{1-x^k}p_{k-1}\end{aligned}$ 由此可以直接写出原式中 $[y^{k-1}]\prod_{j=0}^i \frac{1}{1-y x^j}=\prod_{j=1}^{k-1} \frac{1-x^{i+j}}{1-x^j}$ 故技重施，同样也能解出 $[y^{n-k}] \prod_{j \geq i} \frac{1}{1-y x^j}=\prod_{j=1}^{n-k} \frac{x^i}{1-x^j}$ 现在就有 $g_k=[x^m]\sum_{i \geq 0} i x^i \left( \prod_{j=1}^{k-1} \frac{1-x^{i+j}}{1-x^j}\right)\left( \prod_{j=1}^{n-k} \frac{x^i}{1-x^j}\right)$

虽然把二元 GF 化简为一元，但其形式还不容易处理。可以看到连乘中可以提出 $x^{i(n-k)}$ 和其它与 $i$ 无关的部分。

重点考虑化简 $H_k(x)=\sum_{i \geq 0} i x^{i(n-k+1)} \prod_{j=1}^{k-1} \frac{1-x^{i+j}}{1-x^j}$ 看起来还是不好算，又该 q-analog 出手了。设 $F(x,t)=\sum_{i \geq 0} t^i \prod_{j=1}^{k-1} \frac{1-x^{i+j}}{1-x^j}$ 这样在求出 $t\partial _t F(x,t)$ 后，做换元 $t \mapsto x^{n-k+1}$ 即可得到 $H_k(x)$。我们有结论 $F(x,t)=\prod_{j=0}^{k-1} \frac{1}{1-tx^j }$ 你应该也注意到了，这就是逆用了前一节的推导过程而已。现在可以算出

$t \frac{\partial F(x,t)}{\partial t}= F(x,t)\sum_{j=0}^{k-1} \frac{t x^j}{1-t x^j}$ 于是就得到了 $H_k(x)$： $H_k(x) = \left( \prod_{j=0}^{k-1} \frac{1}{1-x^{n-j}}\right)\sum_{j=0}^{k-1} \frac{x^{n-j}}{1-x^{n-j}}$

再带回 $g_k$ 的表达式中，就得到了

$g_k = [x^m] \left(\prod_{j=1}^n \frac{1}{1-x^j} \right)\sum_{j=0}^{k-1} \frac{x^{n-j}}{1-x^{n-j}}$ 此时就比较容易计算了，把后面的和式拆开就得到了递推 $g_{k+1} = g_k + [x^m]\left(\prod_{j=1}^n \frac{1}{1-x^j} \right) \frac{x^{n-k}}{1-x^{n-k}}$ 直接计算即可，对单个 $k$ 计算此式的复杂度是 $\Theta(m/(n-k))$，总复杂度为 $\Theta(m \log m)$。不过此题模数不让跑 NTT，强行用任意模来做的常数也太大了。

当然，可以利用此题中数据的特殊性质避开 FFT。另外几篇题解中也说到了做法，这里还是提一下：

$\prod_{j=1}^n \frac{1}{1-x^j} \equiv \left( \prod_{j=1}^\infty \frac{1}{1-x^j}\right)\left( \prod_{j=n+1}^m (1-x^j)\right) \pmod{x^{m+1}}$ 前一部分可以利用五边形数定理，以 $\Theta( m^{1.5})$ 的复杂度计算；后一部分把每一项暴力乘上去，复杂度是 $\Theta((m-n)^2)$ 的。