求 \((x^1+x^2+...+x^k)^n\) 的各项系数，要求复杂度 \(\Theta(nk)\)。
前置知识
-
复合函数 \(f[g(x)]\) 的求导：
\(f[g(x)]'=f'[g(x)]g'(x)\)
-
“左乘右导，右乘左导”：
\([f(x)g(x)]'=f(x)g(x)'+f(x)'g(x)\)
做法
设 \(F(x)=x^1+x^2+...x^k\)，那么要求的就是 \(F(x)^k\)。
有 \(F(x)^{k+1}=F(x)^kF(x)\)，两边求导，得到：
\[(k+1)F(x)^kF'(x)=F(x)^kF'(x)+[F(x)^k]'F(x) \]\[kF(x)^kF'(x)=[F(x)^k]'F(x) \]我们取出 \(x^n\) 的系数，可以得到：
\[k\sum_{i=0}^n F(x)^k[i] \times F'(x)[n-i]=\sum_{i=0}^n [F(x)^k]'[i] \times F(x)[n-i] \]\[k\sum_{i=0}^n F(x)^k[i] \times F'(x)[n-i]=\sum_{i=0}^n (i+1) \times F(x)^k[i+1] \times F(x)[n-i] \]把右边 \(i=n\) 的部分分离出来后，可以得到：
\[k\sum_{i=0}^n F(x)^k[i] \times F'(x)[n-i]-\sum_{i=0}^{n-1} (i+1) \times F(x)^k[i+1] \times F(x)[n-i]=(n+1) \times F(x)^k[n+1] \times F(x)[0] \]不难发现 \(F(x),F'(x)\) 都是可以预处理的，所以这就是一个 \(F(x)^k\) 各项系数的递推式。
设 \(f_i\) 表示 \(F(x)\) 的各项系数，\(g_i\) 表示 \(F'(x)\) 的各项系数，\(h_i\) 表示 \(F(x)^k\) 的各项系数，那么可以写成：
\[k \sum_{i=0}^n h_i \times g_{n-i} - \sum_{i=0}^{n-1} (i+1) \times h_{i+1} \times f_{n-i}=(n+1) \times h_{n+1} \times f_0 \] 标签：系数,kF,多项式,sum,times,各项,求导,快速 From： https://www.cnblogs.com/tx-lcy/p/18063437