Symmetric Matrix

题意：
给出n和m，要你构造出满足如下条件的n*n的矩阵，

1、矩阵内的元素A[i][j] = {0,1,2}

2、矩阵内的元素A[i][j] = A[j][i]

3、矩阵内的元素A[i][1]+A[i][2]+A[i][3]+...+A[i][n]=2 对于所有的 i 都成立

4、矩阵内的元素A[i][i]=0 对于所有的 i 都成立

问你有多少中构造方案，构造方案取模m。

思路：
题中的要求，我们可以看出是n个点的邻接矩阵形式。
每个点的度都是2，意味着图是一些环组成的，且不存在自环。
根据数据范围，应该要求O(n)的复杂度，那么应该是个递推。
那么我们考虑f[n]为n个点的方案数。
考虑一下从n-1个点再加入一个点的情况。
就是从前面n-1个点中选取若干个和新加入的第n个点组成环。那么容易得到新加入的第n个点要组成二元环，也就是从前面n-1个点中任选一个，那剩余的n-2就是方案数f[n-2]，这满足乘法原理，方案数就是
然后考虑一般形式。
就是说n-1个点，有k个点形成他们的环的方案数f[k]，那么剩下的n-1-k个点新加入的第n个点这n-k个点形成一个环。容易得到k要≤n-3，因为新加入的去形成二元环的方案数已经计算过了，我们要算的是最少为三元环。
对于n-k个点形成的环，其实是一个圆排列，因为图是对称的，顺时针是逆时针都一样，所以总方案数要除以2
圆排列-百度百科
那么式子就是
把合式内的组合数用阶乘表示化简后得到
那么容易表示出来
可以发现两个式子的和式的分子部分一个是(n-1)! 一个是(n-2)!
那么对f[n-1]的式子两端同乘一个(n-1) 用上面的式子减去下面的式子可以得到(第二个式子乘上之后 两式之间仅差了一项 k=n-3的时候)

左边的移项到右边可以得到

容易得到f[1]=0,f[2]=1,f[3]=1
然后就可以快乐的递推了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1<<17];
int main(){
    ll n,mod;
    while(cin>>n>>mod){
        dp[1]=0,dp[2]=dp[3]=1;
        for(ll i=4;i<=n;i++){
            dp[i]=(((i-1)*(dp[i-1]+dp[i-2])%mod-(i-1)*(i-2)/2*dp[i-3])%mod+mod)%mod;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}