题解 CF223C 【Partial Sums】

nekko

2019-06-10 07:54:09

Solution

就是这玩意: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)$ 的卷积即可