(小声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. 假设我们现在已知图片说明 个点可以构成图片说明 种情况,那么我们求图片说明 个点构成
    (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;
    }