自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:47:48，当前版本为作者最后更新于2023-02-19 16:55:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• 出题人题解。

第一档考虑手玩或爆搜，接下来从第二档讲起。

考虑图 $G$ 上若存在三点 $x,y,z$，若满足 $x \rightarrow y$ 有边，且 $y \rightarrow z$ 有边，那么我们只需改变 $x \rightarrow z$ 的有无边情况，即有边就删无边就加，就能构造出与 $G$ 本质相同的图。那么我们似乎可以得出，图 $G$ 是单图当且仅当其所有点入度为 $0$ 或出度为 $0$。

可这是有问题的，因为存在一个反例，即两点环。不难发现若图中一两点环与外界不联通，显然也无法据此构造出与其本质相同的图。所以需分两种情况讨论。

思考如何计数，对于一个 $n$ 个点的图。令 $f(x)$ 表示 $x$ 个点的单图数，$g(x)$ 表示 $x$ 个点不考虑两点环的单图数，$t(x)$ 表示 $x$ 个点只考虑两点环的单图数。显然有：

先思考 $t(2x)$ 的求解。因为 $t(2x)$ 表示的是 $2x$ 个点划分成 $x$ 对两点环的方案数，我们不妨考虑一对一对选取，那么方案数就是 $\prod\limits_{i=1}^x\dbinom{2x-2(i-1)}{2}$。但这样做会算重，因为其实是与顺序无关的，所以再除以一个 $x!$ 即可。化简后可得 $t(x)=\prod\limits_{2i \leq n}(2i+1)$。

那么 $g(x)$ 怎么求呢？由于所有点要么无入度，要么无出度。考虑这样一种刻画：我们将所有点分为有入度和无入度两类，若前者有 $y$ 个点，则对于前者可能有 $x-y$ 条边，其中一条边都没有是非法的，故有 $(2^{x-y}-1)$ 种方案，将所有点的方案合并，故此时方案数为 $(2^{(x-y)}-1)^y$。所以可得：

故暴力求解可做到 $O(Tn^2 \log n)$。预处理 $g$ 即可做到 $O(n^2 \log n + nT)$。

显然可以优化到 $O(n^2 \log n + T \log n)$。不过并不美丽也无甚价值 。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1010;
 
int T,n,mod,fct[N],ans[N],C[N][N];
inline int pwr(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1) res=(LL)res*x%mod;
		x=(LL)x*x%mod;y>>=1;
	}
	return res;
}
inline void init()
{
	ans[0]=C[0][0]=C[1][0]=C[2][0]=fct[1]=1;
	for(int i=3;i<N;i++) C[i][0]=1,fct[i]=(i&1?(LL)fct[i-2]*i%mod:0);
	for(int i=1;i<N;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	for(int i=1;i<N;i++)
		for(int j=0;j<i;j++)
			ans[i]=(ans[i]+(LL)C[i][j]*pwr(pwr(2,i-j)-1,j)%mod)%mod;				
}

inline void solve()
{
	scanf("%d",&n);
	int res=ans[n];
	for(int i=2;i<=n;i+=2) res=(res+(LL)C[n][i]*fct[i-1]%mod*ans[n-i]%mod)%mod;
	printf("%d\n",res);
}
int main()
{
	scanf("%d%d",&T,&mod);
	init();
	while(T--) solve();
	return 0;
}