ARC134 C - The Majority (500)
1は1以外のと同数のとそれぞれの箱で過半数になる用のボールは位置が固定になる
1以外のボールの個数を$ sum とすると、自由に置けるのは$ a_1 - (k + sum) 個になる
これを新しく$ a_1とする
重複がないように数えると、それぞれのボールは書いてある数毎に独立に置く場所を決められる
$ i 番目の数のボールの置き方は$ {}_{a_i + k - 1}C_{k-1}
ボールに柵を$ k-1個追加して柵の置き方が何通りかという話になる
それぞれの数毎に組み合わせを計算するので$ \mathcal{O}(NK)