Polynomial Sum

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

Polynomial Sum

$
\newcommand{\paren}[1]{\left(#1\right)}
\newcommand{\vec}[1]{\boldsymbol{#1}}
\newcommand{\trans}{^{\mkern-1.5mu\mathsf{T}}}
$

問題

$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} & \vec{0} \\
\vec{c}\trans & 1 \\
\end{matrix}
\right) ^{n+1}
\vec{v}
$$
の第 $k+2$ 成分となる。ここで、$\vec{c} = (c_0, c_1, ..., c_k)\trans$, $\vec{v} = (1, 0, ..., 0)\trans$ である。
$$
M := \left(
\begin{matrix}
D_{k+1}L_{k+1} & \vec{0} \\
\vec{c}\trans & 1 \\
\end{matrix}
\right)
$$
とおくと、$M $ の固有多項式 $p_M(x)$ は、
$$
p_M(x) = (x - a)^{k + 1}(x - 1)
$$
となり、$p_M(M) = O$ である。つまり、$M^{n+1}\vec{v}$ は $x^{n+1} = p_M(x)q(x) + r(x)$ を満たす($k+1$ 次以下の)多項式 $r(x)$ を求めることで、$r(M) \vec{v}$ で計算できる。

$r(x)$ については、以下の 2 式
$$
\begin{align*}
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{align*}
$$
により、ある整数 $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{align*}
S(n) & = (M^{n+1}\vec{v})_{k+2} \\
& = (r(M)\vec{v})_{k+2} \\
& = \sum _{i=0}^{k+1}
\paren{
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}
} (M^i\vec{v})_{k+2} \\
&= \sum _{i=1}^{k+1}
\paren{
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}
} S(i-1)
\end{align*}
$$

として計算ができる。ただし、
$$
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{align*}
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{align*}
$$
といった問題の上位互換である。

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

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