5. 特殊的子集

定义f(n) = 当集合为{1,2,3....n}的时候，特殊的子集按照题目所求的值。
S(n) 为所由能够由{1,2,3,4....n}产生的特殊的子集所构成的集合
1、考虑暴力法
利用生成排列，得到每一个非相邻子集，O(2^n)
2、考虑二进制优化，考虑个p；

3、分析非相邻子集的特点：
n = 1 : {1}
n = 2 : {1}，{2}
n = 3 : {1}，{2}，{3}; {1,3}
n = 4 ：{1}{2}{3}{4}; {1,3},{1,4}{2,4}
.....................................
观察发现：
1、对于每一个S(n)，S(n-1) 总是它的子集。 换句话说，状态时没有后效性的，如果存在状态转移方程，那么就是可以使用dp的方法。
2、考虑不相邻的特性，显然的，我们发现:
对于任意属于S(n-2)的集合A，
{n} U A 总是可以构造成一个子集，
并且可以得出求值以后得到的值 = f(n-2) * n^2
3、从 (2) 我们可以得出所有含有 n 的非相邻集合的所有值。
此时S(n) 被分为两个集合： 1、包含n的集合 2、不包含n的集合
4、包含n的集合通过（2）算出
不包含n的集合的所有求值那就是S(n-1)的值，即f(n-1)
5、得出递推方程：
f(n) = f(n-1) + n^2f(n-2)
然后记得用高精度。

小弱渣来贴个解法OwO
设$f_{n}=\Sigma_{i=1}^{n}T_{i}^{2}$
我们有递推式$f_{n}=f_{n-1}+n^{2}f_{n}+n^{2}(n\ge3),f_{1}=1,f_{2}=5$
待定系数易得$f_{n}-(n+1)f_{n-1}-n=-n[f_{n-1}-nf_{n-2}-(n-1)]=n(n-1)[f_{n-2}-(n-1)f_{n-3}-(n-2)]$
在两边取对数前，不难发现$f_{2}-3f_{1}-2=0,f_{3}-4f_{2}-3=0$
因而有$f_{n}-(n+1)f_{n-1}-n\equiv0$
整理得$f_{n}+1=(n+1)(f_{n-1}+1),n\ge2$
因此$f_{n}+1=(n+1)(f_{n-1}+1)=(n+1)n(f_{n-2}+1)=\cdots=(n+1)n(n-1)\cdots\cdot4\cdot3(f_{1}+1)=(n+1)!$
从而$f_{n}=(n+1)!-1$

超过longlong我也不会啊
python AC代码：
rst=1
n=(int)(input())
for i in range(2,n+2):
rst=rst*i
print(rst-1)