戳我传送


题意:


题目描述:
计算一个满足下列条件的,n x n的矩阵的数量(答案对mod取余)
图片说明

输入描述:
多组输入,每行输入两个整数,n和mod

  • 1 ≤ n ≤ 105
  • 1 ≤ mod ≤ 109
  • The sum of n does not exceed 107.

输出描述:
输出一个整数表示结果


简单回顾邻接矩阵


图片说明
图片说明
图片说明


思路:


了解了数据结构的邻接矩阵后再看这个矩阵满足的条件,矩阵对称和=0 可以让我们联想到无向图的邻接矩阵,=0表示没有自环。而如果边权表示边数的话,每一行的和为2,说明每个点的度为2。显然是由若干个简单环组成的(简单环就是没有公共点公共边的环),环中元素个数至少是2(没有自环)。
既然我们已经发现了规律,接下来可以来递推了:
1.我们考虑用f[i]表示由n个点组成若干个简单环的方法数。
2.图片说明
当n>3,由图片说明图片说明
3.加入第n个点并且取n-1个点中的任何一个点形成2元环,n-1个方案,此时还有n-2个元素,方式总数为图片说明
4.加入第n个点并和前取n-1个点中的任意k-1个点形成k图片说明 元环,图片说明 种方案。此时还有n-k个元素,图片说明 种方案。将取出的k个点全排列,图片说明 种情况,因为1234和2341和3412是一样的,所以可以确定某一位,然后还剩下k-1个点不确定,所以应该是图片说明 种情况。因为是无向图,还要排除首尾一致的情况(即除于2),所以方案数为:图片说明
5.由3、4可以得到总的方案数为:
图片说明
6.化简雨巨已经讲的很清楚了:
图片说明
7.写代码的时候注意不要把图片说明 后面的图片说明 给提出来,不然会wa,因为后面要除2,提出图片说明会丢失精度。


Code:


#include <iostream>
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll f[maxn],n,mod;
int main() {
    js;
    f[1] = 0; f[2] = f[3] = 1;
    while(cin>>n>>mod) {
        for(ll i=4;i<=n;++i)
            f[i] = ((i - 1) * (f[i - 1] + f[i - 2]) - (i - 1) * (i - 2) / 2 * f[i - 3]) % mod;
        cout<<(f[n]+mod)%mod<<endl;
    }
    return 0;
}