問題

https://beta.atcoder.jp/contests/arc102/tasks/arc102_c

K 面サイコロを N 回振る。サイコロは区別しない。各 i (2, 3, ..., 2K) について以下の条件を満たす場合の数を求めよ。

どの異なる2つのサイコロの出目の和も i にならない

制約

1 <= K <= 2000
1 <= N <= 2000

考え方

基礎

まずサイコロを区別しないで N 回振るときの出目の組の場合の数について考える。各サイコロの出目を区別したとして出目を l_1, l_2, ..., l_N とすると、l_1 <= l_2 <= ...<= l_N となるような (l_1, l_2, ..., l_N) の組の数である。これは [1, K] のうち N 個を重複して選ぶ場合の数と同じである。

さて、問題について考える。例として、 K = 14, i = 7 の場合について考えてみる。

「どの異なる2つのサイコロの出目の和も i にならない」という条件について考える。i が奇数の場合と偶数の場合で a + b = i (a <= b) なる (a, b) の組の個数が変わるので多少解法が異なる。まず i が奇数の場合について考える。

(A) a + b = i = 7 となる 2 つの数 (a <= b) の組み合わせは (1, 6), (2, 5), (3, 4) の 3 通りである。この 3 通りの数については条件を満たすためには、それぞれ、(a_i, b_i) のいずれか 1 つ選ぶ、またはどちらも選ばない、ような組み合わせが考えられる。

(B) a + b = i とならない K の出目 (7, 8, 9, 10, 11, 12, 13, 14) については任意個選ぶことができる。

一般化して考えよう。(A)を満たすように選ぶ時の場合の数は (a_i, b_i) の組の個数を n とし、(a_i, b_i) のいずれかから 1 つのみ選ぶ組み合わせを m 選ぶとする。(B)については (A)に含まれない N - 2n の数から N-m 個を重複して選ぶのだが、(A)で選んでいる m 個の数については任意個選んでよいので N-2n+m の数から N-m 個を重複して選ぶ組み合わせの数が求める解である。

${}_{n} \mathrm{C} _m * 2^m * {}_{N-2n+m} \mathrm{H} _{N-m}$