多项式推导（涉及求逆、exp、泰勒展开）：26杭电暑 5-01

image-20260805144507131

由于我又不想打代码，因此我不写了，把题解重新推一遍就算我懂了

我们要求 fk(m)f_k(m)

我们本质上要求满足 0≤x1≤x2≤⋯≤xk≤m0\le x_1\le x_2\le \cdots\le x_k\le m 的：

∏i=1k(axi2+bxi+c)\prod_{i=1}^k(ax_i^2+bx_i+c)

Let P(x)=ax2+bx+cP(x)=ax^2+bx+c，即求：

∏i=1kP(xi)\prod_{i=1}^k P(x_i)

定义多项式 g(j)g(j)，由等比数列求和可以得到：

gj(x)=∑i=0∞P(j)ixi=11−P(j)xg_j(x)=\sum_{i=0}^{\infty}P(j)^ix^i=\frac 1{1-P(j)x}

定义：

F(x)=∏j=0mgj(x)F(x)=\prod_{j=0}^mg_j(x)

那么答案即为 [xk]F(x)[x^k]F(x)

对于乘积的式子，我们最好的办法是直接取对数：

ln⁡F(x)=∑j=0mln⁡(11−P(j)x)=−∑j=0mln⁡(1−P(j)x)\begin{align*} \ln F(x)&=\sum_{j=0}^m\ln \left(\frac 1 {1-P(j)x}\right)\\ &=-\sum_{j=0}^m\ln(1-P(j)x) \end{align*}

有一个经典的泰勒展开：

ln⁡(1−y)=−∑i=1∞yii\ln(1-y)=-\sum_{i=1}^{\infty}\frac{y^i}i

因此上式可以变形为：

ln⁡F(x)=∑j=0m∑i=1∞(P(j)x)ii\ln F(x)=\sum_{j=0}^m\sum_{i=1}^{\infty}\frac{(P(j)x)^i}{i}

交换求和顺序：

ln⁡F(x)=∑i=1∞xii∑j=0mP(j)i\ln F(x)=\sum_{i=1}^{\infty}{x^i\over i}\sum_{j=0}^mP(j)^i

定义：

S(i)=∑j=0mP(j)iS(i)=\sum_{j=0}^mP(j)^i

我们等价于求：

ln⁡F(x)=∑i=1∞S(i)ixi\ln F(x)=\sum_{i=1}^{\infty}{S(i)\over i}x^i

显然，我们求出 S(n)S(n) 的前 nn 项就足够了。

重新考虑 :

P(j)=aj2+bj+c=a(j2+baj+ca)=a((j+b2a)2+ca−b24a2)\begin{align*} P(j)&=aj^2+bj+c\\ &=a\left(j^2+{b \over a}j+{c\over a}\right)\\ &=a\left(\left(j+{b \over 2a}\right)^2+{c\over a}-{b^2 \over 4a^2}\right) \end{align*}

令 B=b2a,C=ca−B2B={b\over 2a},C={c\over a}-B^2。显然 C,BC,B 是常数。于是我们有：

P(j)=a((j+B)2+C)P(j)=a((j+B)^2+C)

现在我们重新求 S(i)S(i):

S(i)=∑j=0mP(j)i=∑j=0mai((j+B)2+C)i=ai∑j=0m∑k=0i(ik)(j+B)2kCi−k=ai∑k=0i(ik)Ci−k∑j=0m(j+B)2k=ai∑k=0ii!k!⋅Ci−k(i−k)!∑j=0m(j+B)2k=aii!⋅∑k=0iCi−k(i−k)!⋅∑j=0m(j+B)2kk!\begin{align*} S(i)&=\sum_{j=0}^mP(j)^i\\ &=\sum_{j=0}^ma^i((j+B)^2+C)^i\\ &=a^i\sum_{j=0}^m\sum_{k=0}^i\binom i k(j+B)^{2k}C^{i-k}\\ &=a^i\sum_{k=0}^i\binom i kC^{i-k}\sum_{j=0}^m(j+B)^{2k}\\ &=a^i\sum_{k=0}^i\frac{i!}{k!}\cdot \frac{C^{i-k}}{(i-k)!}\sum_{j=0}^m(j+B)^{2k}\\ &=\frac{a^i}{i!}\cdot \sum_{k=0}^i{C^{i-k}\over(i-k)!}\cdot{\sum_{j=0}^m(j+B)^{2k} \over k!} \end{align*}

上面第三行的得出我们用到了二项式定理。

这是一个显然的卷积形式，我们定义：

G1i(x)=∑k=0iCkk!xkG2i(x)=∑k=0且k为偶数iUkk!xkG1_i(x)=\sum_{k=0}^i {C^k\over k!}x^k\\ G2_i(x)=\sum_{k=0且k为偶数}^i\frac{U_k}{k!}x^k

那么就有：

S(i)=aii!⋅(G1i(x)×G2i(x))S(i)=\frac{a^i}{i!}\cdot (G1_i(x)\times G2_i(x))

其中：

Uk=∑j=0m(j+B)k      (k为偶数)U_k=\sum_{j=0}^m(j+B)^{k}\;\;\;(k为偶数)

我们现在考虑怎么求 UkU_k

构造指数生成函数：

E(x)=∑r≥0Urr!xr=∑r=0∞∑j=0m(j+B)rxrr!=∑j=0m∑r=0∞((j+B)x)rr!\begin{align*} E(x)&=\sum_{r\ge 0}{U_r\over r!}x^r\\ &=\sum_{r=0}^{\infty}{\sum_{j=0}^m(j+B)^r x^r\over r!}\\ &=\sum_{j=0}^m\sum_{r=0}^{\infty}{((j+B)x)^r\over r!} \end{align*}

一个经典的泰勒展开：

ex=∑i=0∞xii!e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}

因此上式可以变成：

E(x)=∑j=0me(j+B)x=eBx∑j=0m(ex)jE(x)=\sum_{j=0}^me^{(j+B)x}=e^{Bx}\sum_{j=0}^m(e^x)^j

这是一个典型的等比数列求和：

E(x)=eBx⋅(ex)m+1−1ex−1=e(B+m+1)x−eBxex−1\begin{align*} E(x)&=e^{Bx}\cdot{(e^x)^{m+1}-1\over e^x-1}\\ &={e^{(B+m+1)x}-e^{Bx}\over e^x-1} \end{align*}

分母的常数项为0（在 x=0x=0 时，ex−1=0e^x-1=0），所以不能直接求逆。因此我们可以上下同除 xx：

E(x)=e(B+m+1)x−eBxxex−1xE(x)=\frac{\frac{e^{(B+m+1)x}-e^{Bx}}{x}} {\frac{e^x-1} {x}}

我们用泰勒展开对分母推一推：

ex=1+x+x22!+x33!+⋯ex−1x=1+x2!+x23!+⋯e^x=1+x+{x^2\over 2!}+{x^3\over 3!}+\cdots\\ {e^x-1\over x}=1+{x\over 2!}+{x^2\over 3!}+\cdots

因此：

ex−1x=∑i=0∞xi(i+1)!\frac{e^x-1}{x}=\sum_{i=0}^{\infty}\frac{x^i}{(i+1)!}

常数项为1，此时就可以求逆了。

此时我们就求出了 E(x)E(x)

那么：

Ur=[xr]E(x)×r!U_r=[x^r]E(x)\times r!

那么 U0,U2,…,U2nU_0,U_2,\dots,U_{2n} 也可以求了。

回去卷一卷也可以求出 SiS_i 了

最后用多项式exp就可以还原 F(x)F(x) 了。

好了，你已经学会了，尝试写一写吧！