每日一题 4.29 Symmetric Matrix

看题不会 疯狂自闭
看完雨巨和其他大佬的题解后 写出了这道题
写些自己的理解
1、将矩阵的构造转化成图的构造（图的邻接矩阵表示法） 边权值即表示点与点有几条边
于是由条件可知 每个点有且只有两条边（后面的关键） 这个图由几个简单环组成 每个环至少2个点
2、如何由dp[n-1]推出dp[n] 相当于n-1个的点的图变为n个点的图
第一种： n-1个点 选出一个点与新加的点连成环 其他n-2个点自由连
(n-1)dp[n-2]
第二种： n-1个点 选出一个点与新加的点连一条边 然后本身的n-1个点自由连 必有空的一条边来连新加的点
(n-1)dp[n-1]
dp[n]=(n-1)dp[n-2]+(n-1)*dp[n-1] （这是否为答案？）
不是 这里面有重复的构图没有计算
对于第二种 设最先选出的点为x 最后选出来与新加点连的点为y 那么x与y交换之后图是一样的 所有答案要减去这一部分的一半
(n-1)(n-2)dp[n-3]/2
最终答案 dp[n]=(n-1)dp[n-2]+(n-1)dp[n-1] - (n-1)(n-2)*dp[n-3]/2

PS：推出来这些还有一些小问题（我wa了几次） 循环的i要采用ll（乘法可能会超限）（感觉可以采用到处%m来避免）

#include 
#define ll long long
int const N=1e5+5;
using namespace std;
ll n,m,dp[N];
int main()
{
 while(cin>>n>>m)
 {
     dp[1]=0,dp[2]=1,dp[3]=1;
     for(ll i=4;i<=n;++i)
     {
         dp[i]=((i-1)*dp[i-2]+(i-1)*dp[i-1]-(i-2)*(i-1)/2*dp[i-3])%m;
     }
     cout<<(dp[n]+m)%m<<endl;
 }
    return 0;
}