题解 CF223C 【Partial Sums】
nekko
2019-06-10 07:54:09
就是这玩意:https://loj.ac/problem/6261
感觉就是个div2A难度啊?连ntt都不需要
# 题目大意
给定序列 $\{a_n\}$,求其 $k$ 次前缀和的结果
其中 $1 \le n \le 2000, 0 \le k \le 10^9$,答案模 $10^9+7$
# 算法讨论
对于形式幂级数 $A(x)$,以及实数 $p$ 来说,有下式成立:
$$F(x)=A(x)^p \Rightarrow A(x)F'(x)=pF(x)A'(x)$$
对于一个序列 $\{a_n\}$ 来说,求一次前缀和相当于把 $A(x)$ 变为 $\frac{A(x)}{1-x}$
若做 $k$ 次前缀和,相当于乘上 $\frac{1}{(1-x)^k}$,由于乘法具有结合律,只需要考虑后式即可
令 $F(x)=\sum_{n=0}^{\infty}f_nx^n=\frac{1}{(1-x)^k}$,则有:
$$ \begin{aligned} &F(x)=\frac{1}{(1-x)^k}=(1-x)^{-k} \\ \Rightarrow &(1-x)F'(x)=-kF(x)(-1)=kF(x) \\ \Rightarrow &\sum_{n=0}^{\infty}f_{n+1}(n+1)x^n-\sum_{n=1}^{\infty}f_nnx^n=\sum_{n=0}^{\infty} kf_nx^n \end{aligned} $$
即:
$$ \begin{cases} f_0=F(0)=1 \\ f_{0+1}(0+1)=kf_0 \Rightarrow f_1=k \\ f_{n+1}(n+1) - f_nn=kf_n \quad (n \ge 1) \\ \end{cases} $$
最后一个即:
$$ \begin{aligned} &f_{n+1}=\frac{(k+n)f_n}{n+1} \\ \Rightarrow &f_{n}=\frac{(k+n-1)f_{n-1}}{n} \\ \end{aligned} $$
因此可以 $O(n)$ 计算出 $\{f_n\}$ 后,再进行一次 $O(n^2)$ 的卷积即可