#P2833. 数列对计数

    ID: 1939 传统题 1000ms 512MiB 尝试: 48 已通过: 23 难度: 8 上传者: 标签>CF2500提高+/省选-计数 DP记忆化搜索倍数枚举对称性去重

数列对计数

题目描述

考虑两个数列整数列 A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\} 和 B={b1,b2,…,bn}B=\{b_1,b_2,\dots,b_n\},如果从两个数列中各取一项 aia_i 和 bjb_j,其和各不相同且全部在 [1,n2][1,n^2] 内,则称 (A,B)(A,B) 是一个数列对。求本质不同的数列对数。

如果两个数列对在进行以下操作或以下若干操作的组合后相同,那么则认为他们是本质相同的:

  1. 交换 AA 和 BB。
  2. AA 的每个数减一常数,BB 的每个数加一常数。
  3. 交换 AA 中或BB 中任意两个数。

所以,你可以认为 a1=0a_1=0,b1=1b_1=1,A,BA,B 均按升序排列。

输入格式

第一行一个整数 TT 表示测试数据个数; 以下 TT 行每行一个整数 nn 表示序列的长度。

输出格式

对于每个测试数据输出一行,表示本质不同的数列对个数。

4
1
2
3
4
1

1

1

3

样例说明

N=4N=4 时,本质不同的数列对有 33 个:

  1. A={0,1,2,3}A=\{0,1,2,3\},B={1,5,9,13}B=\{1,5,9,13\}。
  2. A={0,1,4,5}A=\{0,1,4,5\},B={1,3,9,11}B=\{1,3,9,11\}。
  3. A={0,1,8,9}A=\{0,1,8,9\},B={1,3,5,7}B=\{1,3,5,7\}。

数据规模与约定

对于 100%100\% 的数据,n≤1000n\le1000。