/ 
実行時間制限: 5 sec / メモリ制限: 1024 MB
配点: 900 点
問題文
以下の条件をともに満たす長さ 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 個ある。
制約
- 1 \leq N \leq 30
- 1 \leq K \leq N^2
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K
出力
問題文中の条件を満たす数列が何種類あるかを出力してください。
ただし、答えは必ず 64 ビット符号付き整数型の範囲に収まります。
入力例 1
1 1
出力例 1
2
N = 1, K = 1 のとき、条件を満たす数列は次の 2 種類です。
- A = (+1, -1)
- A = (-1, +1)
入力例 2
2 3
出力例 2
2
N = 2, K = 3 のとき、条件を満たす数列は次の 2 種類です。
- A = (+1, -1, -1, +1)
- A = (-1, +1, +1, -1)
入力例 3
3 7
出力例 3
6
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)
入力例 4
8 24
出力例 4
568
N = 8, K = 24 のとき、条件を満たす数列は 568 種類あります。
入力例 5
30 230
出力例 5
761128315856702
N = 30, K = 230 のとき、条件を満たす数列は 761128315856702 種類あります。
入力例 6
25 455
出力例 6
0
N = 25, K = 455 のとき、条件を満たす数列はありません。
Score : 900 points
Problem Statement
How many different sequences of length 2N, A = (A_1, A_2, \dots, A_{2N}), satisfy both of the following conditions?
- The sequence A contains N occurrences of +1 and N occurrences of -1.
- There are exactly K pairs of l and r (1 \leq l \leq r \leq 2N) such that A_l + A_{l+1} + \cdots + A_r = 0.
Constraints
- 1 \leq N \leq 30
- 1 \leq K \leq N^2
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number of different sequences that satisfy the conditions in Problem Statement. The answer always fits into the signed 64-bit integer type.
Sample Input 1
1 1
Sample Output 1
2
For N = 1, K = 1, two sequences below satisfy the conditions:
- A = (+1, -1)
- A = (-1, +1)
Sample Input 2
2 3
Sample Output 2
2
For N = 2, K = 3, two sequences below satisfy the conditions:
- A = (+1, -1, -1, +1)
- A = (-1, +1, +1, -1)
Sample Input 3
3 7
Sample Output 3
6
For N = 3, K = 7, six sequences below satisfy the conditions:
- 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 Input 4
8 24
Sample Output 4
568
Sample Input 5
30 230
Sample Output 5
761128315856702
Sample Input 6
25 455
Sample Output 6
0
For N = 25, K = 455, no sequences satisfy the conditions.