Symmetric Matrix

(小声bb)(这题不会,看了好多题解看明白的)
参考博客链接: https://blog.csdn.net/qq_37632935/article/details/81122408
https://ac.nowcoder.com/discuss/87364?type=101&order=0&pos=2060&page=1
题意:构建合法矩阵,然后能够构建多少个
合法矩阵要求: (后面有点挡住了......)
合法矩阵举例:

的有 , 的有, 其中 种为
题解:

1. 把矩阵转换为无向图,并且该无向连通图为环,该无向图可以是多个简单环
   
2. 假设我们现在已知 个点可以构成 种情况,那么我们求 个点构成
   (1)选取 个点与第个点构成环,即
   (2)选取多个点与第进行构图,那么(算了接着写纸上)
   
   
   然后合并上述两种情况得到
   
   因为 有 种情况,所以求和.
   然后这个式子的化简......(高数有点菜),可以看下这个,可能下标有些不一样
   
   额,前半部分可能有些不一样,主要看后面的化简(逃.........)
   时间复杂度:
   另外所需要的前三项在代码中

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long ll;
   const int MAXN=100005;
   ll dp[MAXN];
   int main()
   {
     int n,m;
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         dp[1]=0,dp[2]=dp[3]=1%m;
         for(ll i=4;i<=n;i++)
             dp[i]=((i-1)*(dp[i-1]+dp[i-2])-(i-1)*(i-2)/2*dp[i-3])%m;
         printf("%lld\n",(dp[n]+m)%m);
     }
     return 0;
   }