201174: [AtCoder]ARC117 E - Zero-Sum Ranges 2

Memory Limit:1024 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

求有多少个长度为 $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 $

加入题单

上一题 下一题 算法标签: