关于多项式的做题记录及整理

最近被多项式制裁了，故开此贴记录一些做过的多项式题及多项式trick。

HDU 多校Day3 1004

求 \((a_{2}x^{2}+a_{1}x+a_{0})^t\) 的各项系数，\(t\le 10^7\)。

Solution

设 \(F(x)=a_{2}x^{2}+a_{1}x+a_{0}\)，\(G(x)=F^t(x)\)，那么对 \(G(x)\) 求导得

利用 \([x^i]F'(x)=(i+1)[x^{i+1}]F(x)\)，可以得到 \([x^i]G(x)\) 与 \([x^{i-1}]G(x),[x^{i-2}]G(x)\) 的关系式。

故可 \(O(t)\) 求解。

付公主的背包

待更新。

2024 北京市赛 E

待更新。

2024 ICPC 昆明邀请赛 H

待更新。