Day 136-Q4 | 多項式のCRT的漸化補間

問題

素数 $p = 998244353$ を法として、相異なる $N$ 個の値 $a_1, \dots, a_N$ と、それに対応する値 $r_1, \dots, r_N$ が与えられる。次数 $N-1$ 未満の多項式 $P(x)$ であって、すべての $i$ について $P(a_i) \equiv r_i \pmod p$ を満たすものを求め、係数（次数 $0$ から $N-1$ まで）を mod $p$ で出力せよ。

条件 $P(a_i)\equiv r_i$ は「$P(x)\equiv r_i \pmod{x-a_i}$」と同じ意味であり、$x-a_1,\dots,x-a_N$ は互いに素なので、これは多項式環上の中国剰余定理（CRT）そのものである。整数CRTを「法を1つずつ増やしながら逐次マージする」手順と同じ考え方で $O(N^2)$ 実装せよ。

入力形式

N
a_1 r_1
...
a_N r_N

制約

$1 \le N \le 2000$

$0 \le a_i, r_i < p$

$a_i$ はすべて相異なる

入出力例

入力例1

出力例1

3 2 1

$P(x)=3+2x+x^2$ であり $P(1)=6,\ P(2)=11,\ P(3)=18$ を満たす。

概念図

ヒント（段階的開示）

ヒント1（方向性）

整数のCRTでは「法$m_1$での答え」に「法$m_2$の情報」を1つずつ足し込み、法を$m_1 m_2$に広げていく。多項式でも同じ発想で、モジュラス多項式$M(x)=\prod(x-a_j)$を1次ずつ増やしながら解の多項式$R(x)$を更新できる。

ヒント2（アプローチ）

$i$番目の点を追加するとき、現在の$R(x)$を$a_i$で評価した値と目標値$r_i$とのズレを、$M(a_i)$（$\ne0$が保証される）で割った商が「$M(x)$を何倍して足せばよいか」を表す係数になる。これはニュートンの差分商補間と数学的に同一である。

ヒント3（誘導）

val = poly_eval(R, ai)
diff = (ri - val) % MOD
m_at_a = poly_eval(M, ai)
coef = diff * pow(m_at_a, MOD - 2, MOD) % MOD
# R <- R + coef * M
# M <- M * (x - a_i)

この更新を$N$回繰り返すと、最終的な$R(x)$が求める補間多項式になる。

模範解答 (Python)

import sys

MOD = 998244353


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    a = [0] * N
    r = [0] * N
    for i in range(N):
        a[i] = int(data[idx]) % MOD; idx += 1
        r[i] = int(data[idx]) % MOD; idx += 1

    R = [0]
    M = [1]

    def poly_eval(poly, x):
        res = 0
        for c in reversed(poly):
            res = (res * x + c) % MOD
        return res

    for i in range(N):
        ai = a[i]
        ri = r[i]
        val = poly_eval(R, ai)
        diff = (ri - val) % MOD
        m_at_a = poly_eval(M, ai)
        inv_m = pow(m_at_a, MOD - 2, MOD)
        coef = diff * inv_m % MOD

        new_len = max(len(R), len(M))
        R_new = [0] * new_len
        for k in range(len(R)):
            R_new[k] = R[k]
        for k in range(len(M)):
            R_new[k] = (R_new[k] + coef * M[k]) % MOD
        R = R_new

        M_new = [0] * (len(M) + 1)
        for k in range(len(M)):
            M_new[k] = (M_new[k] - M[k] * ai) % MOD
            M_new[k + 1] = (M_new[k + 1] + M[k]) % MOD
        M = M_new

    coeffs = (R + [0] * N)[:N]
    print(" ".join(str(c % MOD) for c in coeffs))


main()

Step-by-Step 解説

1初期状態は「解なし」のCRT
$R(x)=0,\ M(x)=1$（空積）からスタート。整数CRTで「まだどの法にも制約がない状態」に相当。

2新しい点を1つmergeする
$R(a_i)$と目標値$r_i$の差diffを$M(a_i)$で割った商が「$M(x)$を何倍して足せばa_iでのズレが埋まるか」を表す係数。

3Rの更新は定数倍加算
R_new=R+coef*Mは配列要素ごとの加算で$O(\deg M)$。

4Mの更新は1次式を掛ける
M_new=M*(x-a_i)は係数を1つ上の次数へシフトしつつ$-a_i$倍を加える操作で$O(\deg M)$。

5計算量
$i$番目のステップは$O(i)$なので合計$O(N^2)$。分割統治（部分積木+高速多点評価）で$O(N\log^2N)$まで落とせる。

よくあるミス

ミス	原因	正しい書き方
RとMの配列長が異なるまま加算	短い方で配列外アクセスや高次項の無視	`max(len(R),len(M))`のサイズで確保してから加算
Mの更新でシフトの向きを誤る	xを掛けると全体が1つ高次側にシフトする点を誤解	`M_new[k+1]+=M[k]`、`M_new[k]-=M[k]*a_i`を正しく行う
a_iの重複を仮定せず進める	M(a_i)=0になり逆元計算が破綻	制約で保証されているが入力生成時に重複がないか確認する
modを取り忘れる	他言語移植時に負の値のまま扱ってしまう	減算のたびに`% MOD`を明示する
出力次数が超過	Rの配列長がNを超える場合の考慮不足	`(R + [0]*N)[:N]`で安全に切り詰める

次のステップ

発展: 部分積木（subproduct tree）を構築し、多点評価と多点補間を分割統治で行い$O(N\log^2 N)$に高速化せよ。
発展2: $a_i$に重複がある場合（重複度付きエルミート補間）への拡張を調べよ。

自己評価

完全理解おおむね理解要復習

Day 136-Q4 — 多項式のCRT的漸化補間（Newton形式の逐次マージ）

問題