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 補間でも解ける.