ABC132 D Blue and Red Balls
DPすることを考えても計算量が$ O(NK^2)となり間に合わない. そこで組み合わせ論的に考えてみよう.
まず構造を考察すると, 条件は青いボールと赤いボールのブロックに分けたときに青いボールのブロック数がちょうど$ i個であるということである. また, 青いボールと赤いボールについての場合の数を掛け合わせることで答えは求まる. よって青いボールと赤いボールに分けて考えてみよう.
青いボール
$ i個のブロックのボール数について考える. すると次のような式が立つ.
$ x_1 + x_2 + ... + x_i = Kただし$ x_j \geq 1(1 \leq j \leq i)
これを$ y_j = x_j + 1(1 \leq j \leq i)とおいて変形すると, $ y_1 + y_2 + ... + y_i = K - iただし$ y_j \geq 0(1 \leq j \leq i)となるので重複組み合わせを考えることで$ _{K - 1} C _{K - i}通りであることがわかる.
赤いボール
両端と青いボールの間の合計$ i + 1個のボール数について考える. 青いボールと同様にして考える.
$ x_1 + x_2 + ... + x_i + x_{i+1} = N - Kただし$ x_1, x_{i+1} \geq 0, x_j \geq 1(2 \leq j \leq i)
これを$ y_j = x_j + 1(2 \leq j \leq i)とおいて変形すると, $ y_1 + y_2 + ... + y_i + y_{i+1} = N - K - i + 1となるので重複組み合わせを考えることで$ _{N - K + 1} C _{N - K - i + 1}通りであることがわかる.
計算量は$ O(K)となる.