[ARC117E] Zero-Sum Ranges 2
题意翻译
求有多少个长度为 $2N$ 的序列 $A\ =\ (A_1,\ A_2,\ \dots,\ A_{2N}) $满足以下条件：
- 序列 $A$ 包含 $N$ 个 $+1$ 和 $N$ 个 $-1$ 。
- 恰好有 $k$ 对 $l,r$ 满足 $ A_l\ +\ A_{l+1}\ +\ \cdots\ +\ A_r\ =\ 0 $
$ 1\ \leq\ N\ \leq\ 30 $
， $ 1\ \leq\ K\ \leq\ N^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 $ $ K $
输出格式
問題文中の条件を満たす数列が何種類あるかを出力してください。
ただし、答えは必ず $ 64 $ ビット符号付き整数型の範囲に収まります。
输入输出样例
输入样例 #1
1 1输出样例 #1
2输入样例 #2
2 3输出样例 #2
2输入样例 #3
3 7输出样例 #3
6输入样例 #4
8 24输出样例 #4
568输入样例 #5
30 230输出样例 #5
761128315856702输入样例 #6
25 455输出样例 #6
0说明
### 制約
- $ 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 $ のとき、条件を満たす数列はありません。