题意：

符合下列条件的n*n的矩阵有多少个？(mod m)

每个元素只能为0,1,2；

对称矩阵，主对角线都为0；

每行的和为2。

思路：

看到矩阵的这些特征可以想到把它看作一个无向图的邻接矩阵。

若$A_{i,j}=2$表示i和j之间有两条边，就相当于是两个点的环。

那么每行的和为2的意思就是每个点的度为2，说明这个图全部都是环，每个点属于且仅属于一个环。

可以考虑dp：

f(n)表示n个点时的方案数。

转移：

第n个点在二个点的环内的方案数：$(n-1)*f(n-2)$；

第n个点在三个点的环内的方案数：$C_{n-1}^2*f(n-3)*(\frac{3!}{3})*(\frac{1}{2})$；

第n个点在四个点的环内的方案数：$C_{n-1}^3*f(n-4)*(\frac{4!}{4})*(\frac{1}{2})$；

……

第n个点在k个点的环内的方案数：$C_{n-1}^{k-1}*f(n-k)*(\frac{k!}{k})*(\frac{1}{2})=C_{n-1}^{k-1}*f(n-k)*(k-1)!*(\frac{1}{2})$。

所以，$f(n)=(n-1)*f(n-2)+\frac{1}{2}\sum_{k=3}^nC_{n-1}^{k-1}*f(n-k)*(k-1)!\\\ \ \ \ \ \ \ \ =(n-1)*f(n-2)+\frac{1}{2}\sum_{k=3}^n\frac{(n-1)!}{(n-k)!}*f(n-k)$

令$n-k=t$，得

$$f(n)=(n-1)*f(n-2)+\frac{1}{2}\sum_{t=0}^{n-3}\frac{(n-1)!}{t}*f(t)$$， 同除以$$(n-1)!$$，得 $$n*\frac{f(n)}{n!}=\frac{f(n-2)}{(n-2)!}+\frac{1}{2}\sum_{t=0}^{n-3}\frac{f(n)}{n!}$$

令$g(n)=\frac{f(n)}{n!}$，得

$n*g(n)=g(n-2)+\frac{1}{2}\sum_{t=0}^{n-3}g(t)$。

$(n-1)*g(n-1)=g(n-3)+\sum_{t=0}^{n-4}g(t-1)$。

两式相减，得

$g(n)=(\frac{n-1}{n})g(n-1)+\frac{1}{n}g(n-2)-\frac{1}{2n}g(n-3)$。

将$g(n)=\frac{f(n)}{n!}$代入，得

$f(n)=(n-1)(f(n-1)+f(n-2))-\frac{(n-1)(n-2)}{2}f(n-3)$。

就可以做了。

代码：

typedef long long ll;
ll f[100010];
int main()
{
    ll n,m;
    f[0]=1;f[1]=0;f[2]=1;f[3]=1;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        if(n<=3){printf("%lld\n",f[n]);continue;}
        for(ll i=4;i<=n;i++)
            f[i]=(((i-1)*(f[i-1]+f[i-2])%m)%m-(((i-1)*(i-2)/2)%m*f[i-3])%m+m)%m;
        printf("%lld\n",f[n]);
    }
    return 0;
}