Symmetric Matrix

题意：求满足以下条件的n*n矩阵的个数：
1.所有元素的值属于{0，1，2}；
2.为对称矩阵；
3.每一行的值的和为2；
4对角线的值为0；
结果对m取模。

思路：我们知道无向图的邻接矩阵是对称的，所以将四个条件可以转化为找满足没有自环的n个节点且每个节点有且仅有二条边的无向图有多少个？
我们可以知道这样的无向图是由简单的环组成的，在n个点中，拿第n个节点：
1.与1个节点构成二元环，有（n-1）dp[n-2]种情况。
2.与k个节点构成k+1元环，首先从n-1个节点中取k个节点，环从第n个节点出发，第一次从这k个节点选一个节点连接，从这个节点再在这（k-1）没连接的点中选一个节点连接，以此类推，又因为环逆时针连接与顺时针连接情况相同，所以结果除2，情况dp[n-(k+1)]乘以乘以k!/2;
所以最后dp[n]=(n-1)*（dp[n-1]+dp[n-2])-dp[n-3](n-1)*(n-2)/2(过程请看https://ac.nowcoder.com/discuss/419109);

代码：

#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;

typedef long long ll;

ll dp[100005];

int main()
{
    ll n, m;
    while(cin >> n >> m)
    {
    dp[0]=0;
    dp[1]=0;
    dp[2]=1;
    dp[3]=1;
    for(ll i=4;i<=n;i++)
    {
        dp[i]=(((dp[i-2]+dp[i-1])%m*(i-1))%m-(((i-1)*(i-2)/2)%m)*dp[i-3]%m+m)%m;
    }
    cout << dp[n] << endl;
    }
    return 0;
}