ABC245D - Polynomial division

考え方

$B(x)$の最高次か最低次から順番に決めていくことができる.
(「$C(x)$の最高(低)次数=$A(x)$の最高(低)次数×$B(x)$の最高(低)次数」であるため,一意に決まる)

制約でゼロでないのは最高次なので,次数が高い順に決めていく.つまり,

\begin{aligned}
C_{M + N} &= A_{N} \textcolor{red}{B_{M}} \\
C_{M + N - 1} &= A_{N} \textcolor{red}{B_{M - 1}} + A_{N - 1} B_{M} \\
C_{M + N - 2} &= A_{N} \textcolor{red}{B_{M - 2}} + A_{N - 1} B_{M - 1} + A_{N - 2} B_{M} \\
& \vdots
\end{aligned}
という順に赤字部分が決まる.


まとめると

\begin{aligned}
C_{M + N - i} = \sum_{j=0}^{i} A_{N - i + j} B_{M - j}
\end{aligned}
($A$と$B$の添字の和が$C$の添字に等しくなる全ての場合について和を取る)であり,このステップで未知の$B_{M - i}$は
\begin{aligned}
B_{M - i}
= \frac{1}{A_{N}} \biggl(C_{M + N - i} - \sum_{j=0}^{i - 1} A_{N - i + j} B_{M - j} \biggr)
\end{aligned}
で計算できる.


回答例

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = list(map(int, input().split()))
if M > N:
    A += [0] * (M - N)

B = [0] * (M + 1)
for i in range(M + 1):    
    B[M - i] = C[N + M - i] - sum(B[M - j] * A[N - i + j] for j in range(i))
    B[M - i] //= A[N]

print(*B)