PS:这次比赛一题滚粗 受到了深深地打击。。。。。。。 题意: 给出一个矩阵 矩阵每行的和必须为2 且是一个沿右对角线对称的矩阵 问你大小为n的这样的合法矩阵有多少个。 解题思路: 题目给出的合法矩阵是一个类似与邻接矩阵的样式。 所以应该往这方面去考虑。 每行之和等于2 , 代表每个点都连有两条边,可以有重边 不能有自环。 这说明 每个点属于且仅属于一个环。 因为输入只有一个n 应该要往dp递推的方向上去想。 现在开始找递推式。 定义dp[n]表示n个点构成的合法图的方案数。 思考每加入一个新球,如何从已知状态转移。 考虑从前面的n-1个球中选取一些球和新球组成一个环。 特殊考虑只...