数学也太难了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; }