0252: 辞書で表す疎多項式¶

問題¶

1変数多項式 \(p(x) = \sum_k c_k x^k\) を、ゼロでない係数だけを持つ辞書 {次数: 係数} で表します。例えば \(x^2 - 1\) は {2: 1, 0: -1}、ゼロ多項式は空辞書 {} です。この表現は \(x^{1000} + 1\) のような、次数が高く項数が少ない多項式（疎多項式）を項数に応じた領域で扱えます。

この表現の不変条件は「辞書は値が 0 の項を含まない」です。

次の3つの関数を実装してください。

poly_add(p, q) — 和 \(p + q\) を返します。
poly_mul(p, q) — 積 \(pq\) を返します。係数は畳み込み [(pq)k = \sum p_i \, q_j] で与えられます。
poly_eval(p, x) — 値 \(p(x)\) を返します。

poly_add と poly_mul の返り値も不変条件を満たさなければなりません。

制約¶

次数は非負の整数、係数は 0 でない整数です。
入力の辞書を変更してはいけません。poly_add と poly_mul は新しい辞書を返します。
poly_eval の x は int、float、complex のいずれでもよいものとします。poly_eval({}, x) は 0 を返します。
2つの入力の項数の和を \(m\) とするとき、poly_add は \(O(m)\)、poly_mul は \(O(m^2)\) 時間で動くこと。次数の最大値に比例する時間や領域を使ってはいけません。

例¶

>>> p = {2: 1, 0: -1}    # x^2 - 1
>>> q = {2: -1, 1: 3}    # -x^2 + 3x
>>> sorted(poly_add(p, q).items())
[(0, -1), (1, 3)]
>>> sorted(poly_mul(p, q).items())
[(1, -3), (2, 1), (3, 3), (4, -1)]
>>> poly_add(p, {2: -1, 0: 1})
{}
>>> poly_mul(p, {})
{}
>>> poly_eval(p, 3)
8
>>> poly_eval({1000: 1, 0: 1}, 1)
2
>>> poly_eval({}, 100)
0
>>> p
{2: 1, 0: -1}

発展¶

導関数を返す poly_diff(p) と、合成 \(p(q(x))\) を返す poly_compose(p, q) を追加してください。
繰り返し二乗法で poly_pow(p, n) を実装し、\((x + 1)^{10}\) の係数が二項係数に一致することを確かめてください。

参考¶

『Python Distilled』第2章「マッピング（辞書）」
『Python Distilled』第2章「内包表記」