提供一种不需要多项式/生成函数的做法。
方便起见，记 \(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,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;
}