P5641 开拓者的卓识 题解
题面
原始式子是
\[sum_{k,l,r}=\left\{ \begin{aligned} \sum_{i=l}^r a_i&,k=1\\ \sum_{i=l}^r\sum_{j=i}^rsum_{k-1,i,j}&,k\geq 2\\ \end{aligned} \right. \]考虑求每一个 \(sum_{k,1,r}\) 时，每个位置 \(a_i(1\leq i\leq r)\) 的贡献。相当于是要在两边选 \(k-1\) 个左（右）端点。通过插板法，可以得到这样一个式子：
\[sum_{k,1,r}=\sum_{i=1}^{r}a_i\binom{i+k-2}{k-1}\binom{r-i+k-1}{k-1} \]可以 \(O(n^2)\) 解决。考虑把它化成卷积形式：
令 \(A_i=a_{i+1}\dbinom{i+k-1}{k-1},B_i=\dbinom{i+k-1}{k-1}\)，则
\[sum_{k,1,r}=\sum_{i=0}^{r-1}A_i\times B_{r-1-i} \]化成卷积形式之后可以直接运用NTT \(O(n\log n)\) 解决。
点击查看代码
#include
#include
using namespace std;
const int N=4e5+13,P=998244353,G=3,Gi=332748118;
int n,k,a[N],b[N],r[N];
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)s=1ll*s*a%P;return s;}
inline int Inv(int a){return qpow(a,P-2);}
inline void fft(int *f,int type,int limit){
for(int i=0;i>1]>>1)|((i&1)<<(l-1));
fft(a,1,limit),fft(b,1,limit);
for(int i=0;i