题目描述
https://www.luogu.com.cn/problem/P4705
题解
首先对于 $kin[1,t]$ 我们列出其答案的式子：$$ans_k=frac{sum_{i=1}^n sum_{j=1}^m (a_i+b_j)^k}{nm}$$
观察分子的式子，把它用二项式定理展开：
$$=sum_{x=0}^ksum_{i=1}^nsum_{j=1}^m(_k^x)a_i^xb_j^{k-x}$$
$$=k!sum_{x=0}^k(sum_{i=1}^nfrac{a_i^x}{x!})(sum_{j=1}^mfrac{b_j^{k-x}}{(k-x)!})$$
这两个括号里的式子是等价的，所以我们考虑怎样快速求出对于每个 $kin[1,t]$ ， $sum_{i=1}^na_i^k$
于是我们假设对于每个 $iin[1,n]$ ， $$f_i(x)=sum_{j=0}^{inf}a_i^jx^j
$$ 那上述式子就是 $$(sum_{i=1}^nf_i(x))[x^k]$$
然后做一些转化：$$f_i(x)=frac{1}{1-a_ix}$$
然后我们发现 $$(ln(1-a_ix))'=frac{-a_i}{1-a_ix}$$
设 $g_i(x)=frac{-a_i}{1-a_ix}$ ，那么 $$f_i(x)=-x imes g_i(x)+1$$
所以 $$sum_f(x)=-x imes sum_g(x)+n$$
所以我们考虑怎么算出 $sum_g(x)$
$$sum_g(x)=sum_{i=1}^ng_i(x)$$
$$=sum_{i=1}^n(ln(1-a_ix))'$$
$$=(ln(prod_{i=1}^n(1-a_ix)))'$$
于是我们可以分治+ $Ntt$求出累乘的式子即可
效率： $O(nlog^2n)$