Problem #2912 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

在书架上放有编号为 $1, 2, \dots, n$ 的 $n$ 本书。现将 $n$ 本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。

例如 $n = 3$ 时：原来位置为： $1, 2, 3$ 。放回去时只能为： $3, 1, 2$ 或 $2, 3, 1$ 这两种。

对于每一个 $n$ ，求满足上面的条件的放法有多少？

第 1 行为一个整数 $T$ $(0 \leq T \leq 10) ，表示有$ T$ 组测试数据。

接下来 $T$ 行，每行一个数 $n$ $(0 \leq n \leq 10)$ ，表示有 $n$ 本书。

对于每组测试数据，如果 $n < 8$ ，输出每种放法（每种放法占一行，放法按照字典序从小到大排列），如果 $n \geq 8$ ，只需要输出放法总数。

Input

2
3
8

Output

231
312
14833

算法作业：回溯。

292 人解决，322 人已尝试。

377 份提交通过，共有 716 份提交。

1.5 EMB 奖励。

创建: 13 年，10 月前.

修改: 7 年，3 月前.

最后提交: 2 天，14 小时前.

来源: N/A

dfs

2912. 放书