Symmetric Matrix 题解

太菜了，直接上OEIS

然后发现递推式:

于是。。。完了/x

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m;
int a[N];
int main(){
    while(~scanf("%d%d",&n,&m)){
        a[2]=1,a[3]=1%m,a[4]=6%m;
        for(int i=5;i<=n;++i){
            a[i]=(1LL*(i-1)*(a[i-1]+a[i-2]))%m;
            a[i]=(a[i]-(1LL*(i-1)*(i-2)/2*a[i-3])%m);
            a[i]%=m;
        }
        a[n]=(a[n]+m)%m;
        printf("%d\n",a[n]);
    }
    return 0;
}

还是老老实实推下式子吧。。。

这道题我们最好把矩形看做一个图的邻接矩阵，这样，就很好推了

题目就等价于，每个点有且仅有两条边和其他点连接，但不和自己连接

那么，我们设a[i]表示现在有i个点的情况

假设，我们已经递推出了a[1]-a[i-1]的值，那么，对于新增点i，我们有如下转移:

我们先将新点和以前的一个点先连一条边，然后把它们看做一个整体

有如下讨论：

1.整体相对独立，即两个点之间连两条边

贡献：

2.整体不独立，和剩余的i-2个点组合(整体连两条边相当于两个点分别和其它点连一条边)

贡献：

看了下式子，感觉没问题，但交上去后。。。wa了。。。

为什么？

因为，我们有考虑重复的地方！

因为，我们一开始是选了一个点和新点连边构成一个整体，然后，和其他点讨论。

但，如果整体只和一个点“其他点”连边会怎么样呢？

我们设和新点构成整体的点叫x，“其他点”叫y

那么，“新点和x构整体连y”和“新点和y构整体连x”其实是两个完全一样的情况，但，我们却计算了两次！

所以，我们需要再把"新点和一个点构成整体后只和一个点连边"的情况数减半，即为：

(先从i-1个点选一个点与新点做整体，再选一个点与整体单独相连)(剩下i-3个点自由组合)(方案减半)

然后，就可以了~

(菜鸡是根据答案逆推的，可能比顺推的要简单些qwq)