[問題案] Division of Polynomials

[NyaanNyaan]

問題名: Division of Polynomials

問題概要

多項式f(x) = sum_{i=0..N-1} f_i x^i, g(x) = sum_{i=0..M-1} g_i x^i が与えられます。 次の条件を満たす多項式q(x),r(x)を求めてください。

• f(x) = q(x)g(x) + r(x)
• deg(r) < deg(g)

制約

• 1 <= N,M <= 500,000
• f_{N-1} \not = 0
• g_{M-1} \not = 0

入力

N M
f_0 f_1 ... f_{N-1}
g_0 g_1 ... g_{M-1}

出力

1行目にはu=deg(q)+1, v=deg(r)+1を出力してください。ただし、q(x)=0のときはdeg(q)=-1としてください。(r(x)についても同様です。) 2行目にはq(x)の係数を、3行目にはr(x)の係数を以下の形式で出力してください。

u v
q_0 q_1 ... q_{u-1}
r_0 r_1 ... r_{v-1}

検討事項など

• 多項式除算がなぜか抜けていたので建てました。設定はFPS系の問題と似た感じにしたので無難だと思います。

• 一番の検討事項は入出力形式だと思ったので丁寧に書きました。

[yosupo06]

よさそうです