065 - RGB Balls 2（★7）
選ぶボールの個数を$ r,g,b とすると、条件は
$ K-Y \leq r
$ K-X \leq b
$ r+b \leq Z
の3つ。この条件を満たす全ての$ r,g,b に対しての、$ _R\mathrm{C}_r \cdot _B\mathrm{C}_b \cdot _G\mathrm{C}_{K-r-b} の総和が求める答え。
code:tex
r_i=\begin{cases}
0 & i < K-Y\\
_R\mathrm{C}_i & K-Y \leq i
\end{cases},\
b_i=\begin{cases}
0 & i < K-X\\
_B\mathrm{C}_i & K-X \leq i
\end{cases},\
g_i=_G\mathrm{C}_i
というように定める。これで前2つの条件はOK。
code:tex
rb_i=\begin{cases}
\sum r_jb_{i-j} & i \leq Z\\
0 & Z<i
\end{cases}
とする。$ rb_i はFFTで畳み込みを計算すれば求められる。
求める答えは$ rb と$ gを畳み込みした結果$ \{rgb\} の$ K 項目に他ならない。
一般に、$ c_i=\sum a_jb_{i-j} という形の式はFFTで高速に計算できる。
これはすぐ見えた