B题 解题思路

PS：这次比赛一题滚粗 受到了深深地打击。。。。。。。

题意： 给出一个矩阵 矩阵每行的和必须为2 且是一个沿右对角线对称的矩阵 问你大小为n的这样的合法矩阵有多少个。

解题思路：
题目给出的合法矩阵是一个类似与邻接矩阵的样式。 所以应该往这方面去考虑。
每行之和等于2 , 代表每个点都连有两条边，可以有重边 不能有自环。
这说明 每个点属于且仅属于一个环。
因为输入只有一个n
应该要往dp递推的方向上去想。

现在开始找递推式。
定义dp[n]表示n个点构成的合法图的方案数。
思考每加入一个新球，如何从已知状态转移。
考虑从前面的n-1个球中选取一些球和新球组成一个环。
特殊考虑只取一个旧球的情况，
这种情况下这个旧球有n-1种方案 剩下的n-2个球组成的合法方案数已经求出。
所以这种情况下 方案数为(n-1)f(n-2)
推广到一般情况
当我们取k个旧球，剩下的球与新球组成环时，旧球的取法有C(n-1,k) ，剩下的旧球与新球组成环的方案数有(n-1-k)！种
但是考虑对称性 需要除以2。 又考虑到只取一个球的时候不需要考虑对称性 ，所以把这种情况单独摘出来考虑。
最后得到 dp[n]的递推式就是
dp[n] = (n-1) dp[n-2] + sigma(x:2->n-3)((n-1)!/(2*x!)dp[x])
但是这个东西有一个讨厌的sigma 我们可以通过相减的方法来消除这个sigma。