(小声bb)(这题不会,看了好多题解看明白的)
参考博客链接: https://blog.csdn.net/qq_37632935/article/details/81122408
https://ac.nowcoder.com/discuss/87364?type=101&order=0&pos=2060&page=1
题意:构建合法矩阵,然后能够构建多少个
合法矩阵要求: (后面有点挡住了......)
合法矩阵举例:
的有 , 的有, 其中 种为
题解:
- 把矩阵转换为无向图,并且该无向连通图为环,该无向图可以是多个简单环
- 假设我们现在已知 个点可以构成 种情况,那么我们求 个点构成
(1)选取 个点与第个点构成环,即
(2)选取多个点与第进行构图,那么(算了接着写纸上)
然后合并上述两种情况得到
因为 有 种情况,所以求和.
然后这个式子的化简......(高数有点菜),可以看下这个,可能下标有些不一样
额,前半部分可能有些不一样,主要看后面的化简(逃.........)
时间复杂度:
另外所需要的前三项在代码中#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=100005; ll dp[MAXN]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { dp[1]=0,dp[2]=dp[3]=1%m; for(ll i=4;i<=n;i++) dp[i]=((i-1)*(dp[i-1]+dp[i-2])-(i-1)*(i-2)/2*dp[i-3])%m; printf("%lld\n",(dp[n]+m)%m); } return 0; }