AT_arc117_e [ARC117E] Zero-Sum Ranges 2

[problemUrl]: https://atcoder.jp/contests/arc117/tasks/arc117_e 以下の条件をともに満たす長さ $ 2N $ の数列 $ A\ =\ (A_1,\ A_2,\ \dots,\ A_{2N}) $ は、何種類あるでしょうか？ - 数列 $ A $ は、$ N $ 個の $ +1 $ と $ N $ 個の $ -1 $ で構成される。 - $ A_l\ +\ A_{l+1}\ +\ \cdots\ +\ A_r\ =\ 0 $ となる $ l,\ r $ の組み合わせ $ (1\ \leq\ l\ \leq\ r\ \leq\ 2N) $ はちょうど $ K $ 個ある。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 30 $ - $ 1\ \leq\ K\ \leq\ N^2 $ - 入力はすべて整数 ### Sample Explanation 1 $ N\ =\ 1,\ K\ =\ 1 $ のとき、条件を満たす数列は次の $ 2 $ 種類です。 - $ A\ =\ (+1,\ -1) $ - $ A\ =\ (-1,\ +1) $ ### Sample Explanation 2 $ N\ =\ 2,\ K\ =\ 3 $ のとき、条件を満たす数列は次の $ 2 $ 種類です。 - $ A\ =\ (+1,\ -1,\ -1,\ +1) $ - $ A\ =\ (-1,\ +1,\ +1,\ -1) $ ### Sample Explanation 3 $ N\ =\ 3,\ K\ =\ 7 $ のとき、条件を満たす数列は次の $ 6 $ 種類です。 - $ A\ =\ (+1,\ -1,\ +1,\ -1,\ -1,\ +1) $ - $ A\ =\ (+1,\ -1,\ -1,\ +1,\ +1,\ -1) $ - $ A\ =\ (+1,\ -1,\ -1,\ +1,\ -1,\ +1) $ - $ A\ =\ (-1,\ +1,\ +1,\ -1,\ +1,\ -1) $ - $ A\ =\ (-1,\ +1,\ +1,\ -1,\ -1,\ +1) $ - $ A\ =\ (-1,\ +1,\ -1,\ +1,\ +1,\ -1) $ ### Sample Explanation 4 $ N\ =\ 8,\ K\ =\ 24 $ のとき、条件を満たす数列は $ 568 $ 種類あります。 ### Sample Explanation 5 $ N\ =\ 30,\ K\ =\ 230 $ のとき、条件を満たす数列は $ 761128315856702 $ 種類あります。 ### Sample Explanation 6 $ N\ =\ 25,\ K\ =\ 455 $ のとき、条件を満たす数列はありません。