标签：平移 cdot 多项式 sum dfrac 普通 ans 翻转

【普通多项式】

已知 \(f(x)=\displaystyle\sum_{i=0}^{n}a_ix^i\)，求 \(f(x+c)\) 的系数。

\[\begin{aligned} f(x+c)&=\sum_{i=0}^na_i(x+c)^i\\ &=\sum_{i=0}^na_i\sum_{j=0}^i{i\choose j}x^jc^{i-j}\\ &=\sum_{j=0}^n\dfrac{x^j}{j!}\sum_{i=j}^{n}i!a_i\dfrac{c^{i-j}}{(i-j)!}\\ &=\sum_{i=0}^n\dfrac{x^i}{i!}\sum_{j=i}^{n}j!a_j\dfrac{c^{j-i}}{(j-i)!} \end{aligned} \]

记 \(ans_i=\sum_{j=i}^nj!a_j\dfrac{c^{j-i}}{(j-i)!}\)，目标是求出 \(ans_0\sim ans_n\)。

发现 \(j!a_j\) 和 \(\dfrac{c^{j-i}}{(j-i)!}\) 很像卷积的形式。但是它们不是和一定而是差一定。对于这种非标准形式卷积，我们可以用翻转的方法。令 \(k=j-i\)。

\[ans_i=\sum_{k=0}^{n-i}(k+i)!a_{k+i}\cdot\dfrac{c^k}{k!}=\sum_{l+k=n-i}(n-l)!a_{n-l}\cdot\dfrac{c^k}{k!} \]

开始翻转，令 \(a'_i=(n-i)!a_{n-i}\)，则 \(ans_i=\sum_{l+k=n-i}a'_l\cdot \dfrac{c^k}{k!}\)。

再翻转一次，令 \(ans'_i=ans_{n-i}\)，则 \(ans'_i=\sum_{l+k=i}a'_l\cdot \dfrac{c^k}{k!}\)。所以 \(ans'\) 这个数组可以用 \(a'\) 数组和 \(\dfrac{c^k}{k!}\) 卷出来。

推出 \(ans\) 之后，回到 \(f(x+c)=\sum_{i=0}^n\dfrac{x^i}{i!}ans_i\) 即可。

【下降幂多项式】

已知 \(f(x)=\sum_{i=0}^{n}b_ix^{\underline{i}}\)，求 \(f(x+c)\) 系数。

标签：平移,cdot,多项式,sum,dfrac,普通,ans,翻转
From： https://www.cnblogs.com/FLY-lai/p/18213358