← 返回题目列表

Codeforces · 2108/A

A. 排列热身

中文机器翻译题面 查看原题

对于长度为 $$$n$$$$$$^{\text{∗}}$$$ 的排列 $$$p$$$,我们定义函数:

$$$$$$ f(p) = \sum_{i=1}^{n} \lvert p_i - i \rvert $$$$$$

给你一个数字$$$n$$$。你需要计算有多少 不同 上面写着 计算函数 $$$f(p)$$$ 在考虑时可以采用的值 一切皆有可能 从 $$$1$$$ 到 $$$n$$$ 的数字排列。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500$$$) — 排列中数字的数量。

输出

对于每个测试用例,输出一个整数 - 给定排列长度的函数 $$$f(p)$$$ 的不同值的数量。

示例

输入
复制

5
2
3
8
15
43

输出
复制

2
3
17
57
463

注意

考虑输入的前两个示例。

对于 $$$n = 2$$$,只有 $$$2$$$ 排列 — $$$[1, 2]$$$ 和 $$$[2, 1]$$$。 $$$f([1, 2]) = \lvert 1 - 1 \rvert + \lvert 2 - 2 \rvert = 0$$$,$$$f([2, 1]) = \lvert 2 - 1 \rvert + \lvert 1 - 2 \rvert = 1 + 1 = 2$$$。因此,该函数采用 $$$2$$$ 不同的值。

对于 $$$n=3$$$,已经有 $$$6$$$ 排列:$$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[3, 2, 1]$$$,其函数值分别为$$$0, 2, 2, 4, 4$$$和$$$4$$$,即总共有$$$3$$$值。