题意：构造满足上述4个条件的矩阵，问能构造多少个
分析：可以把这个矩阵看做是无向图的邻接矩阵，那么我们就可以把问题转化为求无向图中所有点的度数都为2的图有多少个。我们考虑(fleft [ n ight ])表示(n)个结点的图满足条件的数量。
我们考虑图中的最后一个点所在的环中有多少个结点:
1.当最后一个环只有两个结点的时候:（为什么不合并为第二种情况呢，因为当一个环只有两个点时，除以(2)就不对了）
(C_{n-1}^{1}ast fleft ( n-2 ight )=left ( n-1 ight )ast fleft ( n-2 ight ))
表示从除最后一个点以外的(n-1)个点中选出1个点与最后一个点形成环，前(n-2)个点形成满足条件的图的总情况有多少
2.考虑最后一个点所在的环有(n-k)个结点的情况，其中(left ( 2leq k且left ( n-k ight )> 2 ight )即left ( 2leq kleq n-3 ight ))
我们可以先从前n-1个结点中选出k个结点形成满足条件的图，那么剩下的(n-k-1)个结点就有((n-k-1)!)种形成链的方式（因为每个点的度为(2)，且这(n-k-1)个结点要与最后一个点形成环，所以这(n-k-1)个结点只会形成链），然后我们再加入最后一个结点与这条链的首尾相连形成环，由于首尾的顺序与形成的环的方式是无关的，所以这里要除以一个(2)将重复的情况去除（比如(1,2,3)三个结点的全排列中就有(1,2,3)和(3,2,1)两种，由于它是无向图，所以在加入最后一个结点(4)之后形成的环都是(1-2-3-4-1)，就有一种情况重复计算了）
所以：公式为：
(C_{n-1}^{k}ast fleft ( k ight )ast frac{left ( n-k-1 ight )!}{2})
最后：
(fleft ( n ight )=left ( n-1 ight )ast fleft ( n-2 ight )+sum_{k=2}^{n-3}C_{n-1}^{k}ast fleft ( k ight )ast frac{left ( n-k-1 ight )!}{2})
(fleft ( n ight )=left ( n-1 ight )ast fleft ( n-2 ight )+sum_{k=2}^{n-3}frac{left ( n-1 ight )!}{k!ast left ( n-k-1 ight )!}ast fleft ( k ight )ast frac{left ( n-k-1 ight )!}{2})
1.(fleft ( n ight )=left ( n-1 ight )ast fleft ( n-2 ight )+sum_{k=2}^{n-3}frac{left ( n-1 ight )!}{k!}ast frac{fleft ( k ight )}{2})，那么有
2.(left ( n-1 ight )ast fleft ( n-1 ight )=left ( n-1 ight )ast left ( n-2 ight )ast fleft ( n-3 ight )+left ( n-1 ight )ast sum_{k=2}^{n-4}frac{left ( n-2 ight )!}{k}ast frac{fleft ( k ight )}{2})
(1式-2式)得：
(fleft ( n-1 ight )ast left ( fleft ( n-1 ight)+fleft ( n-2 ight ) ight )-left ( n-1 ight )*left ( n-2 ight )ast fleft ( n-3 ight )/2)
AC_Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e5+10; 5 #define rep(i,first,second) for(int i=first;i<=second;i++) 6 #define dep(i,first,second) for(int i=first;i>=second;i--) 7 8 int n,m; 9 ll f[maxn]; 10 int main() 11 { 12 while( ~scanf("%d%d",&n,&m)){ 13 if( m==1 ){ 14 printf("0 "); 15 continue; 16 } 17 f[1]=0; 18 f[2]=f[3]=1; 19 rep(i,4,n){ 20 f[i]=((i-1)*(f[i-1]+f[i-2])%m-((ll)(i-1)*(i-2)/2*f[i-3])%m + m)%m; 21 } 22 printf("%lld ",f[n]); 23 } 24 return 0; 25 }
参考博客：here