ABC432-G Sum of Binom(A, B)
$ \sum_i \sum_j \frac{A_i!}{B_j!(A_i-B_j)!} を計算する。畳み込みの形をつくることを目標にする。
$ A_i-B_jが同じものどうしをまとめて計算する。数列$ C=\{i! \#(Aに含まれるiの個数)\}_i, D=\{\frac{1}{(K-j)!}\#(Bに含まれるK-jの個数)\}_j として、その畳み込み$ C \ast D の各要素は$ A_i-B_j=kであるようなペアごとの$ \frac{A_i!}{B_j!}の総和になっている。
あとは$ k \ge 0 の部分を取り出して係数$ \frac{1}{k!}を掛けながら答えに加算していけばよい。
コメント
$ \sum (1+x)^{A_i}が求まらないかな～って思ってたけど分割統治でいけるらしい 自分の知らない方法だった
これPolynomial Taylor Shiftやんけ～～～～～～ 持ってません 解散