atcoder#ARC117E. [ARC117E] Zero-Sum Ranges 2

[ARC117E] Zero-Sum Ranges 2

配点: 900900

問題文

以下の条件をともに満たす長さ 2N2N の数列 A=(A1,A2,,A2N)A = (A_1, A_2, \dots, A_{2N}) は、何種類あるでしょうか?

  • 数列 AA は、NN 個の +1+1NN 個の 1-1 で構成される。
  • Al+Al+1++Ar=0A_l + A_{l+1} + \cdots + A_r = 0 となる l,rl, r の組み合わせ (1lr2N)(1 \leq l \leq r \leq 2N) はちょうど KK 個ある。

制約

  • 1N301 \leq N \leq 30
  • 1KN21 \leq K \leq N^2
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

NN KK

出力

問題文中の条件を満たす数列が何種類あるかを出力してください。 ただし、答えは必ず 6464 ビット符号付き整数型の範囲に収まります。

1 1
2

N=1,K=1N = 1, K = 1 のとき、条件を満たす数列は次の 22 種類です。

  • A=(+1,1)A = (+1, -1)
  • A=(1,+1)A = (-1, +1)
2 3
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 7
6

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)
8 24
568

N=8,K=24N = 8, K = 24 のとき、条件を満たす数列は 568568 種類あります。

30 230
761128315856702

N=30,K=230N = 30, K = 230 のとき、条件を満たす数列は 761128315856702761128315856702 種類あります。

25 455
0

N=25,K=455N = 25, K = 455 のとき、条件を満たす数列はありません。