约定记号：对于生成函数 \(F(x)\) ，我们用 \([k_n(x)]F(x)\) 来表示它的第 \(n\) 项的核函数对应的系数，也就是 \(a_n\)
先把答案式子写出来：
\[ans_k=\frac{\sum_{i = 1}^n\sum_{j = 1}^m(a_i+b_j)^k}{nm}
\]
先处理分子
\[\begin{aligned}
ans_k&=\frac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m(a_i+b_j)^k\&=\frac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m\sum_{l=0}^k\binom{k}{l}a_i^lb_j^{k-l}\&=\frac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m\sum_{l=0}^k\frac{k!}{l!(k-l)!}a_i^lb_j^{k-l}\&=\frac{k!}{nm}\sum_{i=1}^n\sum_{j=1}^m\sum_{l=0}^k\frac{a_i^l}{l!}\frac{b_j^{k-l}}{(k-l)!}\&=\frac{k!}{nm}\sum_{l=0}^k(\sum_{i=1}^n\frac{a_i^l}{l!})(\sum_{j=1}^m\frac{b_j^{k-l}}{(k-l)!})
\end{aligned}
\]
令
\[A(x)=\sum_ix^i\sum_{j=1}^n\frac{a_j^i}{i!}\B(x)=\sum_ix^i\sum_{j=1}^m\frac{b_j^i}{i!}
\]
则
\[\begin{aligned}
ans_k&=\frac{k!}{nm}\sum_{l=0}^k[x^l]A(x)*[x^{k-l}]B(x)\&=\frac{k!}{nm}[x^k](A*B)(x)
\end{aligned}
\]
即用卷积表示原式
现在只需求 \(A(x)\) 和 \(B(x)\) 这两个生成函数就可以得到所有的 \(ans_k\) 了
这里以求 \(A(x)\) 为例，\(B(x)\) 同理
先交换一下求和顺序：
\[\begin{aligned}
A(x)&=\sum_ix^i\sum_{j=1}^n\frac{a_j^i}{i!}\&=\sum_{i=1}^n\sum_j\frac{x^ja_i^j}{j!}
\end{aligned}
\]
令
\[A_1(x)=\sum_ix^i\sum_{j=1}^na_j^i
\]
那么有
\[[x^n]A(x)=\frac{1}{n!}[x^n]A_1(x)
\]
求出 \(A_1(x)\) 即可求出 \(A(x)\)
改写一下上面交换求和顺序的过程：
\[\begin{aligned}
A_1(x)&=\sum_ix^i\sum_{j=1}^na_j^i\&=\sum_{i=1}^n\sum_jx^ja_i^j\&=\sum_{i=1}^n\frac{1}{1-a_ix}
\end{aligned}
\]
这个分式很讨厌，想办法把它搞掉
可以想到 \(\ln‘(x)=\frac{1}{x}\)，想办法往 \(\ln\) 的导数上靠
最直接的思路是：
\[\ln‘(1-a_ix)=\frac{1}{1-a_ix}
\]
带到 \(A_1(x)\) 里：
\[\begin{aligned}
A_1(x)&=\sum_{i=1}^n\frac{1}{1-a_ix}\&=\sum_{i=1}^n\ln‘(1-a_ix)
\end{aligned}
\]
发现这样也不可做，我们得想办法将导数弄到求和外面去
使用 \([f(g(x))]‘=g‘(x)f‘[g(x)]\)，有：
\[[\ln(1-a_ix)]‘=(1-a_ix)\ln‘(1-a_ix)\\]
即
\[[ln(1-a_ix)]‘=\frac{-a_i}{1-a_ix}
\]
用小学知识在 \(\dfrac{-a_i}{1-a_ix}\) 与 \(\dfrac{1}{1-a_ix}\) 之间建立一下关系式：
\[\frac{1}{1-a_ix}=1-x\frac{-a_i}{1-a_ix}
\]
将所得整理，代回 \(A_1(x)\) ：
\[\begin{aligned}
A_1(x)&=\sum_{i=1}^n\frac{1}{1-a_ix}\&=\sum_{i=1}^n(1-x\frac{-a_i}{1-a_ix})\&=\sum_{i=1}^n(1-x*[\ln(1-a_ix)]‘)\&=n-x[\sum_{i=1}^n\ln(1-a_ix)]‘\&=n-x[\ln\prod_{i=1}^n(1-a_ix)]‘
\end{aligned}
\]
现在只需要求 \(\prod_{i=1}^n(1-a_ix)\) ，分治乘就好了
复杂度 \(T(n)=2T(\dfrac{n}{2})+\Theta(n\log n)=\Theta(n\log^2 n)\)