题目分析
题目要求的是：
[sum_{i=1}^nsum_{j=1}^m(a_i+b_j)^x(xin [1,T])
]
利用二项式定理化式子，
[egin{aligned}
&sum_{i=1}^nsum_{j=1}^m(a_i+b_j)^x\
=&sum_{i=1}^nsum_{j=1}^msum_{k=0}^xinom{x}{k}a_i^kb_j^{x-k}\
=&x!sum_{i=1}^nsum_{j=1}^msum_{k=0}^xfrac{a_i^k}{k!}frac{b_j^{x-k}}{(x-k)!}\
=&x!sum_{k=0}^xfrac{sum_{i=1}^na_i^k}{k!}frac{sum_{j=1}^mb_j^{x-k}}{(x-k)!}
end{aligned}
]
发现上面是一个卷积的形式。现在需要我们能快速求出(sumlimits_{i=1}^na_i^k)。
构造(sumlimits_{i=1}^na_i^k)的生成函数：
[egin{aligned}
A(i)&=sum_ja_i^jx^j\
F(x)&=sum_{i=1}^nA(i)
end{aligned}
]
(F)函数的每一项即为(sumlimits_{i=1}^na_i^k)。
化一下式子
[egin{aligned}
F(x)&=sum_{i=1}^nsum_{j}a_i^jx^j\
&=sum_{i=1}^nfrac{1}{1-a_ix}\
&=sum_{i=1}^n1+frac{a_ix}{1-a_ix}\
&=n-xsum_{i=1}^nfrac{-a_i}{1-a_ix}\
&=n-xsum_{i=1}^nleft[ln(1-a_ix)
ight]'\
&=n-xleft[sum_{i=1}^nln(1-a_ix)
ight]'\
&=n-xleft{lnleft[prod_{i=1}^n(1-a_ix)
ight]
ight}'\
end{aligned}
]
(prod_{i=1}^n(1-a_ix))可以用分治FFT(O(nlog^2n))算出。
那么再求ln，求导，乘上x，取负，加上常数项就能得到(F)了。
最后把a,b的生成函数分别除以一下阶乘，再卷积一下即可。