全ての箱について \(1\) が書かれたボールが過半数を占める、というのは箱から \(1\) が書かれたボールとそれ以外の数が書かれたボールを組にして取り除く、という操作を繰り返したとき、\(1\) が書かれたボールだけが残り、かつどの箱も空でないという条件を満たすということと同値です。

それぞれの箱に予め \(1\) が書かれたボールを入れ、 \(1\) が書かれたボールをそれ以外の数が書かれたボールと組にする分を予め取り除いた上で、残ったボールたちを箱に割り振る方法の相乗を求めればよいです。 これは \(\binom{a_1 - 1 - \sum_{i=2}^{N}a_i}{K-1} \prod_{i=2}^{N}\binom{a_i + K-1}{K-1}\) となり、時間計算量 \(O(NK)\) で求められ十分高速です。