数学也太难了QWQ

题目大意：
给一个n*n的矩阵，对于矩阵的每个元素a[i]∈{0,1,2}
其中每行的a[i]的和为2，a[i][i]=0
a[i][j]=a[j][i]
问满足条件的矩阵有多少个。
n<=10^5

思路：
看题目感觉是个递推，但是完全不知道怎么做。
参考了题解：
本题给出的矩阵我们可以联想到图的邻接矩阵（太妙了）
显然根据题目的限制，这是一个每个点最多有两条边的无向图（妙啊）
并且图中没有自环（a[i][i]=0），由于每个点最多两条边，图中只有简单环（不会存在一个点是多个环的公共点）。
我们要求的就是这样的图的数量。

假设我们已经知道f[n-1]表示n-1个点时候的方案数。那么我们现在尝试加入第n个点。
有两种情况：
①组成2元环。C(1,n-1) * f[n-2]
②组成k元环。（k>=3）。
这个稍微复杂点，我们知道一个K元环的方案数为：k!/k=(k-1)!
由于在无向图中，方案数/2。
那么答案就是t=C(k-1,n-1) * (k-1)!/2 * f[n-k]
枚举一下k，∑(k=3-n)t

其实到这里我自己也算不出来
化简一下，得到f[n]=(n-1) * f[n-1] + (n-1) * f[n-2]-(n-1) * (n-2) / 2 * f[n-3]
然后就可以递推了。

代码：

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

    return 0;
}