AtCoder Regular Contest 102：E - Stop. Otherwise...
問題
解法
i の偶奇で場合分けする．
i が奇数の場合，サイコロの目として出てはいけない組み合わせ（禁止された組み合わせ）は (1, i - 1), (2, i - 2), ... となる．この組み合わせの個数を p とおき，これら 2 * p 個の数のうち p ~ (2 * p) の目を一切出さない場合の数を考える．ここで一切出さない目を決める組み合わせは単純に C(2 * p, k) (p <= k <= 2 * p) としてしまうと，禁止された組み合わせが構成出来てしまう場合が出てくるので，2^(2 * p - k) * C(p, k - p) とする．これは，禁止された組み合わせの片方の数が一切出ないものの中で 2 つのうちどちらを一切出ないものにするかを決める通り数 2^(2 * p - k) と禁止された組み合わせの両方の数が一切出ないものを決める組み合わせ C(p, k - p) をかけたもの．これでサイコロの目としてありうる通り数が得られたので，重複組み合わせ H(N - (2 * p - j), K - j) とかければよい．ここで N - (2 * p - j) としているのは，サイコロの目として出すものは N 回のうち最低でも 1 回は出なければならないので，先に 1 回ずつ分配しなければならないから．これを p <= k <= 2 * p を満たす k について計算し足し合わせたものが答えとなる．
i が偶数のとき，サイコロの目として出てはいけない組み合わせは (1, i - 1), (2, i - 2), ... , (i / 2, i / 2) となる．i / 2 の目を 1 回出すか， 1 回も出さないかで場合分けし， i が奇数の時と同様に計算すればよい．このとき，p を p - 1 とし，i / 2 の目を 1 回出す場合，N を N - 1 としなければならないことに注意．
べき乗とコンビネーションは前計算しておくことで O( (N + K)^2 + K^2) となる．
解答
