\begin{aligned}
c_k&=\sum_{i=1}^n\sum_{j=1}^m(a_i+b_j)^k\\
&=\sum_{r=0}^k\sum_{i}\sum_{j}\binom{k}{r}a_i^rb_j^{k-r}\\
&=\sum_{r=0}^kk!\sum_i\frac{a_i^r}{r!}\sum_j\frac{b_j^{k-r}}{(k-r)!}\\
&=k!\sum_{r=0}^kf_rg_{k-r}
\end{aligned}
易知右侧和式为卷积,考虑怎么求
f_r=\frac{1}{r!}\sum a_i^r
用egf容易进入死胡同, 最后可能是一个\sum \sum \exp(a_ix+b_jx) 的形式,几乎不能做
常系数求和,考虑用ogf
f(x)=\sum_{j}x^j\sum_{i}a_i^j=\sum_{i}\sum_{j}(a_ix)^j=\sum_{i}\frac{1}{1-a_ix}
转化为分式求和.
容易想到
\ln'(1-a_ix)=\frac{-a_i}{1-a_ix}
也就是把分式求和转化为 \ln 求和进而转化为 \prod t(x)
注意到
\int \frac{1}{1-a_ix}{\rm d} x = -\frac{1}{a_i}\ln(1-a_ix)
求和后 -\frac{1}{a_i} 的系数仍然不是很好处理.
考虑令
g(x)=\sum_i \frac{-a_i}{1-a_ix}=\sum_i \ln'(1-a_ix)=(\sum_i \ln(1-a_ix))'=\ln'(\prod_i (1-a_ix))
容易解得 f(x)=n-xg(x)