CF2159E
求的是一个:
\([x^k]\frac{(ax^2+bx+c)^n}{1-x}\)
可以分块:
对于所有 \(i\leq B\) 的 \((ax^2+bx+c)^i\) 预处理出。
再处理出所有的 \(i=kB\) 的 \(\frac{(ax^2+bx+c)^{i}}{1-x}\),
也就是 \((ax^2+bx+c)^{i}\) 求出来再做一次前缀和。
至于这个东西是可以线性递推求的,具体大概如下:
\(f=g^n\)
\(f'=ng^{(n-1)}g'\)
\(f'=n\frac{f}{g}g'\)
\(f'g=nfg'\)
\(g\sum_{i=0}f'_ix^i=ng'\sum_{i=0}f_ix^i\)
\(g\sum_{i=0}(i+1)f_{i+1}x^i=ng'\sum_{i=0}f_ix^i\)
考虑第 k 项:
\(\sum_{i=0}(i+1)f_{i+1}g_{k-i}=n\sum_{i=0}(k-i+1)f_ig_{k-i+1}\)
\((k+1)f_{k+1}g_{0}=n\sum_{i=0}^k(k-i+1)f_ig_{k-i+1}-\sum_{i=0}^{k-1}(i+1)f_{i+1}g_{k-i}\)
\((k+1)f_{k+1}g_{0}=\sum_{i=0}^k(nk-ni+n)f_ig_{k-i+1}-\sum_{i=1}^{k}if_{i}g_{k-i+1}\)
\((k+1)f_{k+1}g_{0}=\sum_{i=0}^k(nk-(n+1)i+n)f_ig_{k-i+1}\)
\(f_{k+1}=\frac{\sum_{i=0}^k(nk-(n+1)i+n)f_ig_{k-i+1}}{(k+1)g_0}\)
\(f_{k+1}=\frac{(nk-(n+1)k+n)f_kg_{1}+(nk-(n+1)(k-1)+n)f_{k-1}g_{2}}{(k+1)c}\)
\(f_{k+1}=\frac{(n-k)f_kb+(2n-k+1)f_{k-1}a}{(k+1)c}\)