Cumulative Sum

题意

题解

part1

\(n\) 很大,但 \(m,k\) 很小，这提示了我们。

把 \(f(x,y)\) 看成若干个关于 \(x\) 的多项式，\(f_y(x)\) 。

显然 \(y=0\) 时 \(f_y(x)\) 是一个 \(k\) 次多项式。

考虑由于 \(f_y(x)\leftarrow f_y(x-1)+f_{y-1}(x)\) 。

显然 \(f_y(x)\) 本质上是一个 \(f_{y-1}(x)\) 的前缀和，所以 \(f_y(x)\) 次数是 \(f_{y-1}(x)\) 次数加一。

可以发现 \(f_{y}(x)\) 是一个 \(k+y\) 次多项式。

---

part2

暴力计算 \(f_y(x),x\in[1,k+y]\) 后。(\(\texttt{Complexity : } \mathcal{O(ky)}\)).

考虑 lagrange 插值。

记住 \(x_i\) 值是有规律的时候拉格朗日插值是 \(O(n)\) 的，或者高一点。

分子维护一个suffix,prefix就完事了。

分子发现是每一次全加一，也是可以做的。

这样就完事了。