自动搬运

查看原文

来自洛谷，原作者为

	qweradf **

搬运于2025-08-24 23:10:27，当前版本为作者最后更新于2025-03-14 12:39:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑邻接矩阵，相当于一个 $n\times n$ 的 $01$ 矩阵，每行每列和为 $2$，对角线上全为 $0$，求方案数。

先容斥，钦定对角线的一个子集 $T$ 填 $1$。发现去掉这些 $1$ 后这些位置不能填数，不好处理。

好做的形式是对角线的子集 $\geq 1$，其他位置是 $0$ 或 $1$，这样把钦定的子集减一后对角线和其他格子就没有区别了。

具体地，把钦定的子集减一后，剩下的限制：$n\times n$ 的 $01$ 矩阵，每格填 $0$ 或 $1$，有 $|T|$ 行 $|T|$ 列和为 $1$，其余行列和为 $2$。

记 $f_{i,j,k,l}$ 表示有一个 $(i+j)\times(k+l)$ 的 $01$ 矩阵，要求前 $i$ 行、前 $k$ 列和为 $1$，后 $j$ 行、后 $l$ 列和为 $2$。

状态数是 $O(n^3)$（因为 $i+2j=k+2l$，$l$ 可以用 $i$，$j$，$k$ 表示），转移枚举第一行的 $1$ 填在哪，做到 $O(1)$，所以 $f$ 数组可以 $O(n^3)$ 求出。

容斥的时候钦定对角线的子集 $\geq 1$，其他位置是 $0$，$1$ 或 $2$，这个方案数可以用 $f$ 求出（枚举其他位置哪些填 $2$）。

因此总时空复杂度 $O(n^3)$，做到空间最劣解！！！11。。

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define debug(x) (cerr<<#x": "<<(x)<<endl)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;

bool ST;
const int N=510;
int f[N][N][N];
int n;ll P;
ll CC[N][N];ll C(ll x,ll y){return (x>=y&&y>=0)?CC[x][y]:0;}
bool ED;
int32_t main(){
	debug(fabs(&ST-&ED)/(1<<20));
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>P;
	rep(i,0,n) CC[i][0]=1;
	rep(i,1,n) rep(j,1,i) CC[i][j]=(CC[i-1][j-1]+CC[i-1][j])%P;
	int k;
	f[0][0][0]=1;
	rep(i,0,n) for(int j=0;i+j<=n;j++) rep(l,0,n){
		k=i+2*j-2*l;if(k<0) continue;
		if(i==0){
			if(j==0&&k==0) continue;
			if(k>=2) f[i][j][l]=(f[i][j][l]+(ll)f[i][j-1][l]*(k*(k-1)/2))%P;
			if(k>=1&&l>=1) f[i][j][l]=(f[i][j][l]+(ll)f[i][j-1][l-1]*k*l)%P;
			if(l>=2) f[i][j][l]=(f[i][j][l]+(ll)f[i][j-1][l-2]*(l*(l-1)/2))%P;
		}
		else{
			f[i][j][l]=(f[i][j][l]+(ll)f[i-1][j][l]*k)%P;
			f[i][j][l]=(f[i][j][l]+(ll)f[i-1][j][l-1]*l)%P;
		}
	}
	ll ans=0;
	rep(i,0,n){
		ll ret=0;
		rep(j,0,n-i) (ret+=C(n-i,j)*f[i][n-i-j][n-i-j])%=P;
		ret=ret*C(n,i)%P;
		if(i&1) (ans+=P-ret)%=P;
		else (ans+=ret)%=P;
	}
	cout<<ans<<'\n';
	return 0;
}