#P13698. [ARC117E] Zero-Sum Ranges 2

    ID: 12900 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-一维前缀和计数 DP插板法双射计数Pascal 递推

[ARC117E] Zero-Sum Ranges 2

题目描述

满足以下两个条件的长度为 2N2N 的数列 A=(A1,A2,…,A2N)A = (A_1, A_2, \dots, A_{2N}) 有多少种?

  • 数列 AA 由 NN 个 +1+1 和 NN 个 −1-1 组成。
  • 满足 Al+Al+1+⋯+Ar=0A_l + A_{l+1} + \cdots + A_r = 0 的 (l,r)(l, r) 组合(1≤l≤r≤2N1 \leq l \leq r \leq 2N)恰好有 KK 个。

输入格式

输入以以下格式从标准输入中给出。

NN KK

输出格式

请输出满足题目条件的数列的种数。 注意,答案必定在 6464 位有符号整数范围内。

输入输出样例 #1

输入 #1

1 1

输出 #1

2

输入输出样例 #2

输入 #2

2 3

输出 #2

2

输入输出样例 #3

输入 #3

3 7

输出 #3

6

输入输出样例 #4

输入 #4

8 24

输出 #4

568

输入输出样例 #5

输入 #5

30 230

输出 #5

761128315856702

输入输出样例 #6

输入 #6

25 455

输出 #6

0

说明/提示

限制条件

  • 1≤N≤301 \leq N \leq 30
  • 1≤K≤N21 \leq K \leq N^2
  • 输入均为整数

样例解释 1

当 N=1,K=1N = 1, K = 1 时,满足条件的数列有如下 22 种。

  • A=(+1,−1)A = (+1, -1)
  • A=(−1,+1)A = (-1, +1)

样例解释 2

当 N=2,K=3N = 2, K = 3 时,满足条件的数列有如下 22 种。

  • A=(+1,−1,−1,+1)A = (+1, -1, -1, +1)
  • A=(−1,+1,+1,−1)A = (-1, +1, +1, -1)

样例解释 3

当 N=3,K=7N = 3, K = 7 时,满足条件的数列有如下 66 种。

  • 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)
  • 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

当 N=8,K=24N = 8, K = 24 时,满足条件的数列有 568568 种。

样例解释 5

当 N=30,K=230N = 30, K = 230 时,满足条件的数列有 761128315856702761128315856702 种。

样例解释 6

当 N=25,K=455N = 25, K = 455 时,没有满足条件的数列。

由 ChatGPT 4.1 翻译