#P2786. Ural1142 Relation

    ID: 1894 传统题 1000ms 512MiB 尝试: 307 已通过: 135 难度: 4 上传者: 标签>CF1600普及+/提高-双射计数计数 DP滚动数组高精度加法高精度乘法

Ural1142 Relation

题目描述

dnc1994 要用 < 和 = 两种符号连接变量,一个合法的方案必须满足:

  • 大小关系符合逻辑;
  • 形如 a=b<ca=b<c 与 b=a<cb=a<c 的两个方案被认为相同。

现在 dnc1994 请你求出连接 nn 个变量的方案数。

比如连接 a,b,ca,b,c 三个变量,有如下 13 种方案:

  1. a=b=ca=b=c
  2. a=b<ca=b<c
  3. a<b=ca<b=c
  4. a<b<ca<b<c
  5. a<c<ba<c<b
  6. a=c<ba=c<b
  7. b<a=cb<a=c
  8. b<a<cb<a<c
  9. b<c<ab<c<a
  10. b=c<ab=c<a
  11. c<a=bc<a=b
  12. c<a<bc<a<b
  13. c<b<ac<b<a

输入格式

第一行一个正整数 TT,表示数据组数。 接下来 TT 行,每行一个正整数 nn,表示变量的个数。

输出格式

共 TT 行,每行一个整数表示答案。

2
1
3
1
13

数据规模与约定

对于 100%100\% 的数据,1≤T≤1031\leq T\leq 10^3,1≤n≤501\leq n\leq 50。