题解：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) 的。