問題
要約
- N次多項式 $A(x) = A_N * x^N + A_(N-1) * x^(N-1) + ... + A_1 * x + A_0$
- M次多項式 $B(x) = B_M * x^M + B_(M-1) * x^(M-1) + ... + B_1 * x + B_0$
- これらの積 $C(x) = A(x) * B(x) = C_(N+M) * x^(N+M) + C_(N+M-1) * x^(N+M-1) + ... + C_1 * x + C_0$
条件：
- A(x)とB(x)の各係数は絶対値が100以下の整数
- A(x)とB(x)の最高次の係数は0ではない
- 入力として与えられる$A_0, A_1, ..., A_NとC_0, C_1, ..., C_(N+M)$に対して、条件を満たす$B_0, B_1, ..., B_M$はただ一つ存在する
$A_0, A_1, ..., A_N$と$C_0, C_1, ..., C_(N+M)$が与えられたとき、$B_0, B_1, ..., B_M$を求める。
- N: A(x)の次数
- M: B(x)の次数
- A_i (0 ≤ i ≤ N): A(x)の係数
- B_j (0 ≤ j ≤ M): B(x)の係数（求めるべき値）
- C_k (0 ≤ k ≤ N+M): C(x)の係数
既存投稿一覧ページへのリンク
アプローチ
多項式の乗算を逆算することで未知の多項式B(x)の係数を順に求める。
解法手順
-
入力からN, M, A(x)の係数、C(x)の係数を受け取る。
-
A(x)とC(x)の係数リストを逆順にする。これにより、低次の項から処理を行いやすくなる。
-
B(x)の係数を格納するリストBを初期化する。
-
以下の手順をM+1回繰り返す（i = 0からMまで）：
a. C[i]をA[0]で割った商を計算し、これをB[i]とする。
b. 求めたB[i]を使って、C(x)からA(x)とB[i]の積を引く。具体的には：- j = 0からNまでの各jに対して、C[i+j]からA[j]*B[i]を引く。
-
求めたB(x)の係数リストBを逆順にして出力する。
ACコード
ac.py
def io_func():
# 標準入力から値を読み取る
N, M = map(int, input().split()) # NとMを読み取る
A = list(map(int, input().split())) # A(x)の係数を読み取る
C = list(map(int, input().split())) # C(x)の係数を読み取る
return N, M, A, C
def solve(N, M, A, C):
A = A[::-1] # A(x)の係数リストを逆順にする
C = C[::-1] # C(x)の係数リストを逆順にする
B = [] # B(x)の係数を格納するリストを初期化
for i in range(M + 1):
v = C[i] // A[0] # C[i]をA[0]で割った商を計算
B.append(v) # 計算した商をB(x)の係数としてリストに追加
for j in range(N + 1):
C[i + j] -= A[j] * v # C(x)からA(x)とB[i]の積を引く
return B[::-1] # B(x)の係数リストを逆順にして返す
# メイン処理
if __name__ == "__main__":
N, M, A, C = io_func() # 入力を受け取る
result = solve(N, M, A, C) # 多項式の係数を計算
print(*result) # 結果を出力
###
# N: A(x)の次数
# M: B(x)の次数
# A: A(x)の係数リスト
# C: C(x)の係数リスト
# B: 求めるB(x)の係数リスト
# v: 各ステップで計算される B(x) の係数
# 1. io_func関数: 標準入力から必要なデータを読み取る
# 2. solve関数: 多項式の係数を計算する主要なロジックを実装
# - A(x)とC(x)の係数リストを逆順にする
# - B(x)の係数を低次から順に計算し、C(x)を更新していく
# - 計算されたB(x)の係数リストを逆順にして返す
# 3. メイン処理: io_func関数とsolve関数を呼び出し、結果を出力する
覚書
A(x) = 2x + 1 と B(x) = 3x + 4 の積 C(x) を求め、A(x) と C(x) から B(x) を復元する。
C(x) を計算する
C(x) = A(x) * B(x) = (2x + 1)(3x + 4)
= 6x^2 + 8x + 3x + 4
= 6x^2 + 11x + 4
係数を比較する
A(x) = 2x + 1 なので、A1 = 2, A0 = 1
C(x) = 6x^2 + 11x + 4 なので、C2 = 6, C1 = 11, C0 = 4
B(x) の係数を求める
-
最高次の係数: B1 = C2 / A1 = 6 / 2 = 3
-
次の係数: (C1 - A1B0) / A0 = (11 - 23) / 1 = 5
しかし、B(x) = 3x + 4 なので、実際は B0 = 4 -
C(x) の係数は A(x) と B(x) の係数の積の和になる
-
B(x) の係数は C(x) と A(x) の係数を使って順に求められる