# 反演

# 二项式反演

如果有 :
$f(x) = \sum _{i = 0} ^{n} (-1) ^{i} * \binom{n}{i} * g(i)$

那么有 :
$g(x) = \sum _{i = 0} ^{n} (-1) ^{i} * \binom{n}{i} * f(i)$

# 单位根反演

$$[k|n] = \frac{1}{k} \sum _{i = 0} ^{k - 1} \left( \omega _{k} ^{n} \right) ^{i}$$

# 类欧几里得算法

$$\begin{aligned} f(a,b,c,n) & = \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor \\ g(a,b,c,n) & = \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor ^{2} \\ h(a,b,c,n) & = \sum _{i = 0} ^{n} i \ast \left\lfloor \frac{ai + b}{c} \right\rfloor \\ \end{aligned}$$

# $f(a,b,c,n) = \sum _{i = 0} ^{n} \lfloor \frac{ai + b}{c} \rfloor$

(1). 对于 $a \ge c$ 或 $b \ge c$ 时

$$\begin{aligned} f(a,b,c,n) & = \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor \\ & = \sum _{i = 0} ^{n} \left\lfloor \frac{ ( \lfloor a / c \rfloor c + a \% c ) \, i + \lfloor b / c \rfloor c + b \% c } {c} \right\rfloor \\ & = \sum _{i = 0} ^{n} \left( \lfloor a / c \rfloor i + \lfloor b / c \rfloor + \left\lfloor \frac{ (a \% c) \, i + b \% c } {c} \right\rfloor \right) \\ & = \frac{n \, (n + 1)}{2} * \lfloor a / c \rfloor c + (n + 1) * \lfloor b / c \rfloor c + \sum _{i = 0} ^{n} \left\lfloor \frac{ (a \% c) \, i + b \% c } {c} \right\rfloor \\ & = \frac{n \, (n + 1)}{2} * \lfloor a / c \rfloor c + (n + 1) * \lfloor b / c \rfloor c + f(a \% c,\, b \% c,\, c,\, n) \\ \end{aligned}$$

(2). 对于 $a < c$ 且 $b < c$ 时

记 $m=\lfloor \frac{an+b}{c} \rfloor$ , 则有 :

$$\begin{aligned} \\ f(a,b,c,n) & = \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor \\ & = \sum _{i = 0} ^{n} \sum _{j = 0} ^ {m-1} \left[ j < \left\lfloor \frac{ai + b}{c} \right\rfloor \right] \\ & = \sum _{i = 0} ^{n} \sum _{j = 0} ^ {m-1} \left[ j + 1 \leq \frac{ai + b}{c} \right] \\ & = \sum _{i = 0} ^{n} \sum _{j = 0} ^ {m-1} \left[ jc + c - b \leq ai \right] \\ & = \sum _{i = 0} ^{n} \sum _{j = 0} ^ {m-1} \left[ \frac{jc + c - b - 1}{a} < i \right] \\ & = \sum _{j = 0} ^ {m-1} \sum _{i = 0} ^{n} \left[ \frac{jc + c - b - 1}{a} < i \right] \\ & = \sum _{j = 0} ^ {m-1} \left( n - \left\lfloor \frac{jc + c - b - 1}{a} \right\rfloor \right) \\ & = nm - f(c,\, c-b-1,\, a,\, m - 1) \\ \end{aligned}$$

综上，可得以下式子 :

$$\begin{aligned} f(a,b,c,n) = \begin{cases} \frac{n \, (n + 1)}{2} * \left\lfloor \frac{a}{c} \right\rfloor + (n + 1) * \left\lfloor \frac{b}{c} \right\rfloor + f(a \% c,\, b \% c,\, c,\, n) & , a \ge c \;or\; b \ge c \\ nm - f(c,\, c-b-1,\, a,\, m - 1) & , a < c \;and\; a < c \end{cases} \end{aligned}$$

# $g(a,b,c,n) = \sum _{i = 0} ^n \lfloor \frac{ai + b}{c} \rfloor ^2$

(1). 对于 $a \ge c$ 或 $b \ge c$ 时

$$\begin{aligned} g(a,b,c,n) & = \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor ^{2} \\ & = \sum _{i = 0} ^{n} \left\lfloor \frac{ ( \lfloor a / c \rfloor + a \% c ) i + ( \lfloor b / c \rfloor + b \% c ) }{c} \right\rfloor ^ {2} \\ & = \sum _{i = 0} ^{n} \left( \lfloor a / c \rfloor i + \lfloor b / c \rfloor + \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor \right) ^ {2} \\ & = \sum _{i = 0} ^{n} \left( ( \lfloor a / c \rfloor i + \lfloor b / c \rfloor ) ^{2} + \left\lfloor \frac{ (a \% c) i + (b \% c) }{c} \right\rfloor ^ {2} + 2 i ( \lfloor a / c \rfloor + \lfloor b / c \rfloor ) \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor \right) \\ & = \sum _{i = 0} ^{n} ( \lfloor a / c \rfloor i + \lfloor b / c \rfloor ) ^{2} + \sum _{i = 0} ^{n} \left\lfloor \frac{ (a \% c) i + (b \% c) }{c} \right\rfloor ^ {2} + \sum _{i = 0} ^{n} 2 ( \lfloor a / c \rfloor i + \lfloor b / c \rfloor ) \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor \\ & = \sum _{i = 0} ^{n} \lfloor a / c \rfloor ^{2} i ^{2} + \sum _{i = 0} ^{n} \lfloor b / c \rfloor ^{2} + \sum _{i = 0} ^{n} 2 i \lfloor a / c \rfloor \lfloor b / c \rfloor + \sum _{i = 0} ^{n} \left\lfloor \frac{ (a \% c) i + (b \% c) }{c} \right\rfloor ^ {2} + \sum _{i = 0} ^{n} 2 \lfloor a / c \rfloor i \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor + \sum _{i = 0} ^{n} 2 \lfloor b / c \rfloor \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor \\ & = \lfloor a / c \rfloor ^{2} \sum _{i = 0} ^{n} i ^{2} + \sum _{i = 0} ^{n} \lfloor b / c \rfloor ^{2} + 2 \lfloor a / c \rfloor \lfloor b / c \rfloor \sum _{i = 0} ^{n} i + \sum _{i = 0} ^{n} \left\lfloor \frac{ (a \% c) i + (b \% c) }{c} \right\rfloor ^ {2} + 2 \lfloor a / c \rfloor \sum _{i = 0} ^{n} i \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor + 2 \lfloor b / c \rfloor \sum _{i = 0} ^{n} \left\lfloor \frac{ (a \% c) i + b \% c }{c} \right\rfloor \\ & = \frac{n (n + 1) (n \ast 2 + 1) \lfloor a / c \rfloor ^{2}} {6} + (n + 1) \lfloor b / c \rfloor ^{2} + n (n+1) \lfloor a / c \rfloor \lfloor b / c \rfloor + g(a \% c,\, b \% c,\, c,\, n) + 2 \lfloor a / c \rfloor h(a \% c,\, b \% c,\, c,\, n) + 2 \lfloor b / c \rfloor f(a \% c,\, b \% c,\, c,\, n) \end{aligned}$$

(2). 对于 $a < c$ 且 $b < c$ 时

已知 $x ^{2} = \left( 2 \sum _{i = 1} ^{x} i \right) -x = \left( 2 \sum _{i = 0} ^{x} i \right) -x$

记 $m = \lfloor \frac{an + b}{c} \rfloor$, 则有 :

$$\begin{aligned} g(a,b,c,n) & = \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor ^{2} \\ & = 2 \sum _{i = 0} ^{n} \sum _{j = 0} ^{ \lfloor \frac{ai + b}{c} \rfloor} j - \sum _{i = 0} ^{n} \left\lfloor \frac{ai + b}{c} \right\rfloor \\ & = 2 \sum _{i = 0} ^{n} \sum _{j = 1} ^{m} j \left[ \; j < \left\lfloor \frac{ai + b}{c} \right\rfloor \; \right] - f(a, b, c, n) \\ & = 2 \sum _{i = 0} ^{n} \sum _{j = 1} ^{m} j \left[ \; \frac{jc + c - b - 1}{a} < i \; \right] - f(a, b, c, n) \\ & = 2 \sum _{i = 0} ^{n} \sum _{j = 0} ^{m-1} (j+1) \left[ \; \frac{jc + c - b - 1}{a} < i \; \right] - f(a, b, c, n) \\ & = 2 \sum _{j = 0} ^{m-1} \sum _{i = 0} ^{n} (j+1) \left[ \; \frac{jc + c - b - 1}{a} < i \; \right] - f(a, b, c, n) \\ & = 2 \sum _{j = 0} ^{m-1} (j+1) \left( n - \left\lfloor \frac{jc + c - b - 1}{a} \right\rfloor \right) - f(a, b, c, n) \\ & = 2 n \sum _{j = 1} ^{m} j - 2 \sum _{j = 0} ^{m-1} (j+1) \left\lfloor \frac{jc + c - b - 1}{a} \right\rfloor - f(a, b, c, n) \\ & = n m (m + 1) - 2 h(c,\, c - b - 1,\, a,\, m - 1) - 2 f(a,\, b,\, c,\, m-1) - f(a, b, c, n) \end{aligned}$$

综上，可得以下式子 :

$$\begin{aligned} g(a,b,c,n) = \begin{cases} \frac{n (n + 1) (n \ast 2 + 1) \lfloor a / c \rfloor ^{2}} {6} + (n + 1) \lfloor b / c \rfloor ^{2} + n (n+1) \lfloor a / c \rfloor \lfloor b / c \rfloor + g(a \% c,\, b \% c,\, c,\, n) + 2 \lfloor a / c \rfloor h(a \% c,\, b \% c,\, c,\, n) + 2 \lfloor b / c \rfloor f(a \% c,\, b \% c,\, c,\, n) \\ n m (m + 1) - 2 h(c,\, c - b - 1,\, a,\, m - 1) - 2 f(a,\, b,\, c,\, m-1) - f(a, b, c, n) & , a < c \;and\; a < c \end{cases} \end{aligned}$$

# $h(a,b,c,n) = \sum _{i=0}^{n} i \left\lfloor \frac{ai+b}{c} \right\rfloor$

(1). 对于 $a \ge c$ 或 $b \ge c$ 时

$$\begin{aligned} h(a,b,c,n) & = \sum _{i = 0} ^{n} i \ast \left\lfloor \frac{ai + b}{c} \right\rfloor \\ & = \sum _{i = 0} ^{n} i \ast \left\lfloor \frac{ ( \lfloor a / c \rfloor c + a \% c ) \, i + \lfloor b / c \rfloor c + b \% c } {c} \right\rfloor \\ & = \sum _{i = 0} ^{n} i \ast \left( \lfloor a / c \rfloor i + \lfloor b / c \rfloor + \left\lfloor \frac{ (a \% c) \, i + b \% c } {c} \right\rfloor \right) \\ & = \sum _{i = 0} ^{n} i ^{2} \lfloor a / c \rfloor + \sum _{i = 0} ^{n} i \lfloor b / c \rfloor + \sum _{i = 0} ^{n} i \ast \left\lfloor \frac{ (a \% c) \, i + b \% c } {c} \right\rfloor \\ & = \frac{n (n + 1) ( n * 2 +1) \lfloor a / c \rfloor}{6} + \frac{n (n + 1) \lfloor b / c \rfloor}{2} + h(a \% c,\, b \% c,\, c, n) \end{aligned}$$

(2). 对于 $a < c$ 且 $b < c$ 时

记 $G = \left\lfloor \frac{jc + c - b - 1 }{a} \right\rfloor$, 则有 :

$$\begin{aligned} h(a,b,c,n) & = \sum _{i = 0} ^{n} i \ast \left\lfloor \frac{ai + b}{c} \right\rfloor \\ & = \sum _{i = 0} ^{n} i \sum _{j = 0} ^{m - 1} \left[ j < \left\lfloor \frac{ai + b}{c} \right\rfloor \right] \\ & = \sum _{i = 0} ^{n} \sum _{j = 0} ^{m - 1} i \ast \left[ \frac{jc + c - b - 1}{a} < i \right] \\ & = \sum _{j = 0} ^{m - 1} \sum _{i = 0} ^{n} i \ast \left[ G < i \right] \\ & = \sum _{j = 0} ^{m - 1} \sum _{i = G + 1} ^{n} i \\ & = \frac{1}{2} \sum _{j = 0} ^{m - 1} (n + G + 1)(n - G) \\ & = \frac{1}{2} \sum _{j = 0} ^{m - 1} (n ^ {2} - G ^ {2} + n - G) \\ & = \frac{1}{2} \sum _{j = 0} ^{m - 1} n ^ {2} - \frac{1}{2} \sum _{j = 0} ^{m - 1} G ^ {2} + \frac{1}{2} \sum _{j = 0} ^{m - 1} n - \frac{1}{2} \sum _{j = 0} ^{m - 1} G \\ & = \frac{1}{2} \left( n ^ {2} m + n m - f(c,\, c - b - 1,\, a, m - 1) - g(c,\, c - b - 1,\, a, m - 1) \right) \\ & = \frac{1}{2} n m (n + 1) - \frac{1}{2} f(c,\, c - b - 1,\, a, m - 1) - \frac{1}{2} g(c,\, c - b - 1,\, a, m - 1) \\ \end{aligned}$$

综上，可得以下式子 :

$$\begin{aligned} h(a,b,c,n) = \begin{cases} \frac{n (n + 1) ( n * 2 +1) \lfloor a / c \rfloor}{6} + \frac{n (n + 1) \lfloor b / c \rfloor}{2} + h(a \% c,\, b \% c,\, c, n) & , a \ge c \;or\; b \ge c \\ \frac{1}{2} n m (n + 1) - \frac{1}{2} f(c,\, c - b - 1,\, a, m - 1) - \frac{1}{2} g(c,\, c - b - 1,\, a, m - 1) & , a < c \;and\; a < c \end{cases} \end{aligned}$$

# 总结:

$$\begin{aligned} f(a,b,c,n) & = \begin{cases} \frac{n \, (n + 1)}{2} * \left\lfloor \frac{a}{c} \right\rfloor + (n + 1) * \left\lfloor \frac{b}{c} \right\rfloor + f(a \% c,\, b \% c,\, c,\, n) & , a \ge c \;or\; b \ge c \\ nm - f(c,\, c-b-1,\, a,\, m - 1) & , a < c \;and\; a < c \end{cases} \\ g(a,b,c,n) & = \begin{cases} \frac{n (n + 1) (n \ast 2 + 1) \lfloor a / c \rfloor ^{2}} {6} + (n + 1) \lfloor b / c \rfloor ^{2} + n (n+1) \lfloor a / c \rfloor \lfloor b / c \rfloor + g(a \% c,\, b \% c,\, c,\, n) + 2 \lfloor a / c \rfloor h(a \% c,\, b \% c,\, c,\, n) + 2 \lfloor b / c \rfloor f(a \% c,\, b \% c,\, c,\, n) \\ n m (m + 1) - 2 h(c,\, c - b - 1,\, a,\, m - 1) - 2 f(a,\, b,\, c,\, m-1) - f(a, b, c, n) & , a < c \;and\; a < c \end{cases} \\ h(a,b,c,n) & = \begin{cases} \frac{n (n + 1) ( n * 2 +1) \lfloor a / c \rfloor}{6} + \frac{n (n + 1) \lfloor b / c \rfloor}{2} + h(a \% c,\, b \% c,\, c, n) & , a \ge c \;or\; b \ge c \\ \frac{1}{2} n m (n + 1) - \frac{1}{2} f(c,\, c - b - 1,\, a, m - 1) - \frac{1}{2} g(c,\, c - b - 1,\, a, m - 1) & , a < c \;and\; a < c \end{cases} \end{aligned}$$

$\Huge$

$$\begin{aligned} \end{aligned}$$

$$\begin{aligned} \end{aligned}$$