链接：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

在这里插入图片描述
输入描述:

The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.

输出描述:

For each test case, print an integer which denotes the result.

示例1
输入

3 1000000000
100000 1000000000

输出

1
507109376

备注:

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

题解：

利用OEIS求解：

我们先枚举出n=2,3,4,5,6时，答案分别是多少？
n=2 sum=1
n=3 sum=1
n=4 sum=6
n=5 sum=22
然后在OEIS直接搜1 1 6 22就会弹出这个如图
OEIS是一个整数数列线上大全，可以利用数列中部分值查询这个数列以及公式
（第一次用OEIS，才发现有这么一个宝贝）
在这里插入图片描述
根据如图，可以得到式子
a(n)= ( n-1 ) * ( a(n - 1 ) * a( n-2 ) ) - ( n-1 ) * ( n-2 ) * a(n-3) /2
对了不要忘了mod m

具体证明：

不大会。。。
结合多篇文章，自己的理解
矩阵我们可以转化成图的构造，你就想想图的那个邻接矩阵表示法，（也就是常用的二维数组存边）边权值表示点与点有几条边

因为对称位置值相同（题目所给），每个点都会连接两个边，形成环，又因为对角线为0，所以边不可能连接自身
a[n]表示有n个点的情况
我们要做的时候，如果从a[n-1]推到a[n]，也就是从n-1个点推到n个点
两种情况：
第一种： n-1个点选出一个的点与第n个点连接形成环，其他n-2个点自由连接
(n-1)f[n-2]
第二种：n-1个点选出一个点x与第n个点连接成边，但是暂不成环，只是单向连，然后n-1个点自由连，一定会出现空出一个点y只连接一次，再和第n个点相连
（n-1）f[n-1]

答案就是f[n]=(n-1)*( f[n-2]+f[n-1] )
但是情况二会存在重复，
因为矩阵是关于对角线对称的，第二种情况中，咱们一开始选出的点是x，最后选出的是y，如果倒过来先选的y后选的x，最后出来的矩阵效果是一样的，选x的方案数是n-1，选y是n-2,剩下n-3个数自由选择，倒过来会重复，所以减去 的值要除以2
所以重复的部分是(n-1)(n-2)f[n-3]/2

最后合在一起就OK了：a(n)= ( n-1 ) * ( a(n - 1 ) * a( n-2 ) ) - ( n-1 ) * ( n-2 ) * a(n-3) /2

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn = 1e5 +5;
ll n,m;
ll f[maxn];
void init()
{
    f[1]=0;
    f[2]=1;
    f[3]=1;
}
int main(){
    while(cin>>n>>m)
    {
        init();//初始化
        for(ll i=4;i<=n;i++)
        {
            f[i]=((i-1)*f[i-2]+(i-1)*f[i-1]-(i-2)*(i-1)/2*f[i-3])%m;
        }
        printf("%lld\n",(f[n]+m)%m);
    }
    return 0;
}