自动搬运

查看原文

来自洛谷，原作者为

	A_zjzj AFO：2019.9~2025.01.22

搬运于2025-08-24 21:55:20，当前版本为作者最后更新于2023-12-01 16:38:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题面

提供一种不需要多项式/生成函数的做法。

方便起见，记 $P(G)=0/1$ 表示 $G$ 是否不存在非平凡自同构。

首先发现对于图 $G$ 的补图 $G'$，显然 $P(G)=P(G')$。

那么边数的最大值 $=\frac{n(n-1)}{2}-$ 边数的最小值。

显然，边数最小的时候 $G'$ 是一个森林（要求每棵树 $T$ 都不同构且 $P(T)=1$）。

在此基础之上，对于两棵树 $T_1,T_2(P(T_1)=P(T_2)=1)$，若 $T_1$ 的点数 $< T_2$ 的点数，那么选择 $T_1$ 一定优于选择 $T_2$。

容易发现，当且仅当 $n=2,3,4,5,6$ 的时候不存在合法的树，所以，特判 $n\le 6$，下面考虑 $n\ge 7$。

所以，我们可以从小到大枚举 $T$ 的点数 $n$，然后把剩下的点尽量用 $n$ 个点的树覆盖，直到覆盖不了为止。

但是，这样会产生一个问题，就是可能最后会剩下 $m$ 个点，那么我们只需要把这 $m$ 个点加入到最大的那棵树上就行了。

由于 $n\ge 7$，所以一定可以加上最后的几个点。

至此，仅剩下如何求出 $n$ 个点的合法树的个数 $f_n$ 的问题。

在判断树同构的时候，我们可以以重心为根做一遍树哈希（如果有两个就都做一遍），然后比较哈希值判断两棵树是否同构。

所以在这里，我们同样可以使用重心来避免算重。

我们用 $h_n$ 表示 $n$ 个点的有根树的本质不同的个数，$g_{n,m}$ 表示用 $m$ 个点，组成若干互不相同的大小 $\le n$ 的子树的方案数。

转移：

$$h_{n}=g_{n-1,n-1}\\ g_{n,m}=\sum\limits_{i=0}^{\min\{h_n,\lfloor \frac{m}{n}\rfloor \}}\binom{h_n}{i}\times g_{n-1,m-n\times i} \\ f_{n}= \left\{ \begin{array}{cc} g_{\frac{n-1}{2},n-1} & 2\nmid n \\ g_{\frac{n}{2}-1,n-1}+\binom{g_{\frac{n}{2}-1,\frac{n}{2}-1}}{2} & 2 | n \\ \end{array} \right. $$

$h,g$ 的转移应该没什么问题。

$f$ 的转移，就是要考虑一下树的重心的个数，分类讨论以下即可。

然后用 python 简单跑一下，发现 $n=266$ 的时候 $\sum\limits_{i=1}^{n}f_i$ 已经超过了 $10^{100}$，足够了，python 代码：

import math
mod=int(1e9+7)
n=266
def C(n,m):
	if 0>m or m>n:
		return 0
	ans=1
	for i in range(m):
		ans=ans*(n-i)//(i+1)
	return ans
f=h=[0 for i in range(0,n+1)]
g=[[0 for j in range(0,n+1)] for i in range(0,n+1)]
g[0][0]=1
for i in range(1,n+1):
	h[i]=g[i-1][i-1]
	for j in range(0,n+1):
		for k in range(j//i+1):
			g[i][j]+=C(h[i],k)*g[i-1][j-i*k]
for i in range(1,n+1):
	f[i]=g[(i-1)//2][i-1]
	if i%2==0:
		f[i]+=C(g[i//2-1][i//2-1],2)
	print(i,f[i])
T=int(input())
for t in range(T):
	m=int(input())
	if m>1 and m<6:
		print(-1)
		continue
	if m==6:
		print(9)
		continue
	ans=m*(m-1)//2-m
	res=0
	for i in range(1,n+1):
		if m<i:
			break
		cnt=min(m//i,f[i])
		res+=cnt
		m-=i*cnt
	print((ans+res)%mod)

然后就套个高精度模板就行了，注意要压位，不然跑不过去。

#include<bits/stdc++.h>
using namespace std;
/*  struct bign (bigint=bigbig=__int128, block>=8) */
const int N=3e2,mod=1e9+7;
int T,n=266;
bign m,f[N],g[N][N],h[N];
bign C(bign n,int m){
	if(0>m||bign(m)>n)return bign(0);
	bign ans(1);
	for(int i=0;i<m;i++){
		ans=ans*(n-i)/(i+1);
	}
	return ans;
}
bign min(bign x,bign y){
	return x<y?x:y;
}
int main(){
	freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	g[0][0]=1;
	for(int i=1;i<=n;i++){
		h[i]=g[i-1][i-1];
		for(int j=0;j<=n;j++){
			for(int k=0;i*k<=j;k++){
				g[i][j]+=C(h[i],k)*g[i-1][j-i*k];
			}
		}
	}
	for(int i=1;i<=n;i++){
		f[i]=g[(i-1)/2][i-1];
		if(i%2==0)f[i]+=C(g[i/2-1][i/2-1],2);
		// debug(i,f[i]);
	}
	for(cin>>T;T--;){
		cin>>m;
		if(m>bign(1)&&m<bign(6)){
			puts("-1");
			continue;
		}
		if(m==bign(6)){
			puts("9");
			continue;
		}
		int ans=m%mod;
		ans=(ans*(ans-1ll)/2-ans+mod)%mod;
		for(int i=1;i<=n;i++){
			if(m<bign(i))break;
			bign cnt=min(m/i,f[i]);
			(ans+=cnt%mod)%=mod;
			m-=cnt*i;
		}
		printf("%d\n",ans);
	}
	return 0;
}

我用的 bign 模板