# floor sum

２乗を求めようとしたらもうちょい広げられそうなことに気付いたのでメモ

パラメタ $c, d$ も加えてみる
$$F(n,m,a,b,c,d) = \sum_{i=0}^{n-1}i^c \left\lfloor \frac{ai+b}{m} \right\rfloor^d$$
を考えてみよう。

$$
\begin{aligned}
F(n,m,a+xm,b+ym,c,d)&=\sum_{i=0}^{n-1}i^c \left(\left\lfloor \frac{ai+b}{m} \right\rfloor+xi+y\right)^d\\
&=\sum_{i=0}^{n-1}\sum_{p,q,r\geq 0, p+q+r=d} i^c\frac{d!}{p!q!r!}\left\lfloor \frac{ai+b}{m} \right\rfloor^p (ix)^qy^r\\
&=\sum_{p,q,r\geq 0, p+q+r=d} \frac{d!}{p!q!r!}x^qy^rF(n,m,a,b,q+c,p)
\end{aligned}
$$

よって $0 \leq a, b < m$ の場合を解けばいい

$$
\begin{aligned}
y &= \left\lfloor \frac{a(n-1)+b}{m} \right\rfloor\\
p_k(n) &= \sum_{i=0}^{n-1} i^k\\
\end{aligned}
$$
と置く。

$$
\begin{aligned}
F(n,m,a,b,c,d)&=\sum_{i=0}^{n-1}i^c \left\lfloor \frac{ai+b}{m} \right\rfloor^d\\
&=\sum_{x=1}^y (x^d-(x-1)^{d}) \sum_{\lfloor(ai+b)/m\rfloor\geq x} i^c\\
&=\sum_{x=1}^y (x^d-(x-1)^{d}) \left(p_c(n) - p_c\left(\left\lceil \frac{mx-b}{a}\right\rceil\right)\right)\\
&=\sum_{x=0}^{y-1} ((x+1)^d-x^{d}) \left(p_c(n) - p_c\left(\left\lceil \frac{mx+m-b}{a}\right\rceil\right)\right)\\
\end{aligned}
$$
となる
$$
\left\lceil \frac{mx+m-b}{a}\right\rceil= \left\lfloor \frac{mx+m-b+a-1}{a}\right\rfloor
$$
と $p_k(x)$ が$x$についての$k+1$次の多項式であることを用いると $F(n,m,a,b,c,d)$ は $F(y,a,m,m-b+a-1,p,q), p + q \leq c + d$ の和で表せる。
前計算で$p_k(n)$の係数を計算しておく。
$F(n,m,a,b,c,d)$が求めたいものとする。
$k = c + d$ とする。
すると上の計算量は 再帰の回数が $O(\log n + \log a)$、一つの呼び出しの中で計算する項の数が$O(k^2)$, 一つの項の計算に $O(k^2)$ かかるのでクエリ辺の計算量は $O(k^4(\log n + \log a))$ となる。

22/08/22 [既出](https://loj.ac/p/138)と知った&提出眺めてたら三乗あるっぽい

$\sum_{i = 0}^{d-1} C(d, i) F(y, a, m, m - b + a - 1, c)$ とかを前計算しておくと$O(k^3 (\log a + \log n))$ になる