AtCoder Regular Contest 117
翻译中…
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.
翻译中…
样例
Input #1
1 1
Output #1
2
For $N = 1, K = 1$, two sequences below satisfy the conditions:
- $A = (+1, -1)$
- $A = (-1, +1)$
Input #2
2 3
Output #2
2
For $N = 2, K = 3$, two sequences below satisfy the conditions:
- $A = (+1, -1, -1, +1)$
- $A = (-1, +1, +1, -1)$
Input #3
3 7
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)$
Input #4
8 24
Output #4
568
Input #5
30 230
Output #5
761128315856702
Input #6
25 455
Output #6
0
For $N = 25, K = 455$, no sequences satisfy the conditions.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。