Polynomial Sum

djdolls さんの公式 QPOLYSUM - Editorial - CodeChef Discuss を、固有多項式を用いた一般的な方法で導出する。

問題

$a$ を任意の整数、$p_k(x)$ を整数係数 $k$ 次多項式とするとき、以下の総和 $$S(n) := \sum _{i=0}^{n} a^i p_k(i)$$ を求めることを考える。ただし、$$p_k(x) := \sum _{i=0}^k c_i x^i \ (c_k \ne 0)$$ とする。

方法

まず、$n \times n$ の下三角 Pascal 行列を $L_n$、対角成分が $a$ であるような $n \times n$ の対角行列を $D_n$ と書くことにする。

このとき、総和 $S(n)$ は、以下のベクトル $$\left( \begin{matrix} D_{k+1}L_{k+1} & \boldsymbol{0} \\ \boldsymbol{c}^{\mkern-1.5mu\mathsf{T}} & 1 \\ \end{matrix} \right) ^{n+1} \boldsymbol{v}$$ の第 $k+2$ 成分となる。ここで、$\boldsymbol{c} = (c_0, c_1, ..., c_k)^{\mkern-1.5mu\mathsf{T}}$, $\boldsymbol{v} = (1, 0, ..., 0)^{\mkern-1.5mu\mathsf{T}}$ である。$$M := \left( \begin{matrix} D_{k+1}L_{k+1} & \boldsymbol{0} \\ \boldsymbol{c}^{\mkern-1.5mu\mathsf{T}} & 1 \\ \end{matrix} \right) $$ とおくと、$M $ の固有多項式 $p_M(x)$ は、$$ p_M(x) = (x - a)^{k + 1}(x - 1)$$ となり、$p_M(M) = O$ である。つまり、$M^{n+1}\boldsymbol{v}$ は $x^{n+1} = p_M(x)q(x) + r(x)$ を満たす($k+1$ 次以下の)多項式 $r(x)$ を求めることで、$r(M) \boldsymbol{v}$ で計算できる。

$r(x)$ については、以下の 2 式 $$\begin{aligned} x^{n+1} & \equiv 1 \pmod{(x-1)}, \\ x^{n+1} & \equiv r_a(x) := \left\{ \begin{matrix} \sum _{i=0}^k \binom{n+1}{i} \binom{n-i}{k-i} a^{n - i + 1} (-1)^{k - i}x^i & (n \ge k)\\ x^{n+1} & (n < k) \end{matrix} \right.\pmod{(x-a)^{k+1}} \end{aligned} $$ により、ある整数 $c$ を用いて、$$r(x) = c(x-a)^{k+1} + r_a(x)$$ と書ける。ここで、$$r(1) = c(1 - a)^{k+1} + r_a(1) = 1 $$ により、$$c = \left\{ \begin{matrix} \frac{1 - r_a(1)}{(1 - a)^{k+1}} & (a \ne 1) \\ \binom{n+1}{k+1} & (a = 1) \end{matrix} \right. $$ となる。$a=1$ の時は、$x^{n+1} \pmod{(x-a)^{k+2}}$ の $x^{k+1}$ の係数である。

(補足: $c$ は $\sum_{i=0}^{n-k} \binom{i + k}{i}a^i$ と一致する)

よって、 $$\begin{aligned} S(n) & = (M^{n+1}\boldsymbol{v})_{k+2} \\ & = (r(M)\boldsymbol{v})_{k+2} \\ & = \sum _{i=0}^{k+1} \left( c\binom{k+1}{i}(-a)^{k+1-i} + \binom{n+1}{i}\binom{n-i}{k-i} a^{n-i+1} (-1)^{k-i} \right) (M^i\boldsymbol{v})_{k+2} \\ &= \sum _{i=1}^{k+1} \left( c\binom{k+1}{i}(-a)^{k+1-i} + \binom{n+1}{i}\binom{n-i}{k-i} a^{n-i+1} (-1)^{k-i} \right) S(i-1) \end{aligned}$$ として計算ができる。ただし、$$c = \left\{ \begin{matrix} \frac{1 - \sum _{i=0}^k \binom{n+1}{i} \binom{n-i}{k-i} a^{n - i + 1} (-1)^{k - i}}{(1 - a)^{k+1}} & (a \neq 1) \\ \binom{n+1}{k+1} & (a = 1) \end{matrix} \right. $$ である。

補足

これは、$$\begin{aligned} A_k(n) &= \sum _{i=0}^{n} i^k\ (a = 1, p_k(x) := x^k) \\ B_k(n) &= \sum _{i=0}^{n} a^i i^k\ (p_k(x) := x^k) \end{aligned} $$ といった問題の上位互換である。

mod が素数であれば、上の式を用いて $A_k(n), B_k(n)$ は $O(k \log\log{k})$ で計算ができるので、$n = 10^{18}, k = 10^7$ のような制約でも出題できる。

ただし、Lagrange 補間でも解ける。