Symmetric Matrix题解

一天终于搞懂了，还是手动推了一边公式。
题意，就是题目要求让你构建合法的矩阵，然后问你种类数。
题解：这道题我们可以把这个图看成邻接矩阵，是个无向图，首先，我们看来数据范围，不超过1e7，那么肯定是个递推，或者动态规划，或者就是规律，然后我们分析，我们给点赋值，不就是在图里面加边权吗，当我们需要加第N个点的时候，是不是要构成除自环以外的其他任何几元环，二圆环比较特殊，我们当加入第N个点的是时候，是不是需要前面任何一个点都可以，那么就是有N-1个选法，是不是还有N-2个点是原来的就是dp【n-2】，二元环总数就是（n-1）dp[n-2],那么后面的多元环呢，我们选着K个点和第N个构成多元环，那么就是选择方法C（n-1,k）,然后是不是这个K个点又可以有序排列出他的种类数就是K！，那么剩下是不是c-1-k个点，就有dp[n-1-k]然后就是C(n-1,k)k!*dp[n-k-1],但是不对，为什么，首先我们是环，是不是会有重复得排列出来的点呢，列如，512345，543215，是不是就重复了，所有最后我们要>>1,最后答案就是

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
ll dp[maxx];
int main()
{
    fio;
    ll n,m;
    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-1]+dp[i-2])-(i-1)*(i-2)/2*dp[i-3])%m;
  //  dp[i]=((i-1)*(dp[i-1]+dp[i-2])-(i-1)*(i-2)/2*dp[i-3])%m;
          //  dp[i]=(dp[i]+m)%m;
        }
        cout<<(dp[n]+m)%m<<endl;
    }
    return 0;
}