P5947 [POI 2003] Trinomial 一般情况讨论

Leo235 · 2026-02-11 22:00:26 · 算法·理论

Trinomial 一般性讨论

本文重点在于对此类题目的一般情况（没有模3）解的讨论，因此推导过程并非最优！

二项式定理、求导（高阶导数）、组合。

首先，看到 (x^2+x+1)^n，一个高次多项式，就想到把它求高阶导给“简化”一下。由于求的是 x^i 的系数，为完全消除 x^i 的影响仅保留系数值，我们不妨对其求 i 阶导数：\ 记 F(x)=(x^2+x+1)^n，则通过二项式定理得

F(x)=[x^2+(x+1)]^n=\sum_{k=0}^n \binom{n}{k} x^{2k}(1+x)^{n-k}

好的，现在不妨对 F(x) 的每一项求 i 阶导并取 x=0，得

F^{(i)}(0)=\sum_{k=0}^n \binom{n}{k} \frac{\mathrm{d}^i}{\mathrm{d}x^i} [x^{2k}(1+x)^{n-k}] \Big|_{x=0}

固定 k 值，记 f(x)=x^{2k}，g(x)=(1+x)^{n-k}，使用莱布尼茨公式求出 i 阶导数：

(fg)^{(i)}(0)=\sum_{t=0}^{i}\binom{i}{t} f^{(t)}(0)g^{(i-t)}(0)

当且仅当 t=2k 时，f^{(t)}(0)\ne 0，此时 f^{(t)}(0)=(2k)!。

同时当且仅当 i-t\le n-k 时，g^{(i-t)}(0)\ne 0，此时 g^{(i-t)}(0)=\frac{(n-k)!}{(n-k-i+t)!}。

\binom{i}{2k} (2k)!\times \frac{(n-k)!}{(n-k-i+2k)!}

好的，现在我们将这个 i 阶导部分代会原函数，得

F^{(i)}(0)=\sum_k \binom{n}{k} \binom{i}{2k} (2k)!\times \frac{(n-k)!}{(n-k-i+2k)!}

则系数 ^{[1]} a_i=\frac{F^{(i)}(0)}{i!}，为

\sum_k \binom{n}{k} \frac{\binom{i}{2k} (2k)!}{i!}\times \frac{(n-k)!}{(n-k-i+2k)!}

由于 \binom{i}{2k}=\frac{i!}{(2k)!(i-2k)!}，则

a_i=\sum_k \binom{n}{k} \frac{(n-k)!}{(i-2k)!(n-k-i+2k)!} = \sum_k \binom{n}{k} \binom{n-k}{i-2k}

结合上面推出来的范围，整理一下，最终得到

a_i=\sum_{k=0}^{\left \lfloor \frac{i}{2} \right \rfloor } \binom{n}{k} \binom{n-k}{i-2k}

现在，我们就得到了此问题的一般解，在数据范围允许的情况下，可以进行 O(n) 求解。

[1] : 有一定数学基础的同学可以去看一下首一多项式的高阶导数与系数、商式的恒等转换及余式定理、泰勒级数、幂级数的商式级数展开已获得更为详细的证明。