2. 問題概要 AtCoder 食堂では, 円の主菜が 種類 円の副菜が 種類 i Ai j Bj ある. ちょうど 円になる, 主菜と副菜一つずつの組合せがい くつあるかを出力せよ. k 3. 畳込み ちょうど 円になる組合せの数を とすると, 主菜で 円の物を選んだ時, 副菜として 円の物を選べばよ く, となる. 但し, とおく. k Ck i k − i =Ck ∑ i=0 k Ai Bk−i = = 0A0 B0 このような を, と の畳込み (convolution) という.C A B 4. 畳込みから多項式乗算へ ここで, , を係数とする多項式 を考えると, その積は で定まる. A B g(x) = , ∑ i=0 N Ai x i h(x) = ∑ j=0 N Bj x j (g ∗ h)(x) = g(x) ∗ h(x) = ∑ i=0 N ∑ j=0 N Ai