式子摘自洛谷用户璀璨星空1的题解(Orz。
这题就是求没有等价点的图的最大边数。
考虑原图没有等价点,则补图也没有等价点,求原图最大边数等价于总边数减求补图最小边数。
$n=1$ 答案显然为 $0$;
$n=2、3$ 答案显然为 $-1$;
$n=4$ 时原图和补图都需要联通,所以边数都至少为 $3$ ,而经过枚举,大小为 $4$ 的树不可能没有对称点,所以答案为 $-1$;
$n=5$ 时原图和补图都需要连通,总边数为 $10$,可能情况有 $4/6$ 或 $5/5$ ,经枚举可以知道不可能不存在对称点,所以答案也为 $-1$;
$n=6$ 时原图和补图都需要连通,总边数为 $15$,$5/10$ 时容易得到五个点的树不可能不存在对称点,而 $6/9$ 时可以构造一个环上链长度为 $1,2,3$ 的基环树,所以答案为 $9$;
$n\ge 7$ 时至少都可以构造一个从中心像三个方向发散长度为 $2,3,n-3$ 的树,所以一定存在答案。
我们贪心考虑一下, $n\ge 7$ 时补图的每个联通块一定都是小于 $n$ 的树构成,不选大小为 $6$ 的基环树的原因是容易证明一定有小于或者等于这种选法的答案。
那么我们求出大小为 $n$ 的无标号无根无对称点树的个数就行了,设这个个数序列为 $U$,考虑能不能通过递推求出 $U$ ,发现由于无根不好求,那就用有根的来求。
设有根无对称点的个数为 $R$ ,考虑讨论重心位置:
1、 $n\bmod 2=1$ 时,重心唯一,减去有子树大于二分之一的情况即 $R_n-\frac{1}{2}\sum_1^{n-1}R_{i}R_{n-i}$;
2、 $n\bmod 2= 0$ 时,除开减去有子树大于二分之一的情况以外,还要除去两棵树互为同构的情况即 $R_n-\frac{1}{2}\sum_1^{n-1}R_{i}R_{n-i}-\frac{1}{2}R_{\frac{n}{2}}$。
快速算出 $R_i$ 即可。
又 $ R_n=\sum_{(\sum_{i=1}^{n-1}(i\times x_i))+1=n}\prod_{i=1}^{n-1}{R_i\choose x_i}$ ,考虑生成函数 $F(x)=x\prod_{i=1}^\infty(1+x^i)^{R_i}$。
两边同时取 $\ln$,得到 $\ln F(x)=\ln x+\sum_{i=1}^\infty (R_i\ln(1+x^i))$;
同时求导,得到 $ \dfrac{F’(x)}{F(x)}=\dfrac1x+\sum_{i=1}^{\infty}(R_i\cdot\dfrac{ix^{i-1}}{1+x^i})$;
所以 $xF’(x)=F(x)+F(x)\sum_{i=1}^{\infty}(R_i\cdot\dfrac{ix^{i}}{1+x^i})$;
对比两边 $x^n$ 的系数,得到:
$ R_n=\dfrac1{n-1}\cdot(\sum_{i=1}^{n-1}(R_{n-i}(\sum_{d|i}(-1)^{\frac id+1}dR_d)))$。
直接算 $R,U$,贪心数数即可。
#include<bits/stdc++.h>
#define LL __int128
const int LEN = 100;
using namespace std;
typedef long long ll;
int T;
LL read() {
LL val=0,cnt=0;
char ch=' ';
while(!('0'<=ch&&ch<='9')) ch=getchar();
while('0'<=ch&&ch<='9') val=(val<<1)+(val<<3)+(ch-'0'),ch=getchar(),++cnt;
if(cnt>=100) return 0;
return val;
}
void write(LL val) {
if(val==0) {
printf("0\n");
return;
}
int tmp=val;
stack<char> st;
while(!st.empty()) st.pop();
while(tmp>=1) st.push((tmp%10)+'0'),tmp/=10;
while(!st.empty()) printf("%c",st.top()),st.pop();
printf("\n");
}
LL n,r[105],u[105];
const LL mod=1e9+7;
int main() {
LL a,b;
r[1]=r[2]=1;
for(int i=3;i<=100;++i) {
for(int j=1;j<i;++j) {
LL anss=0;
int sqt=sqrt(j);
for(int l=1;l<=sqt;++l) {
if(j%l) continue;
anss+=((j/l)&1?1:-1)*l*r[l];
if(j/l!=l) anss+=(l&1?1:-1)*(j/l)*r[j/l];
}
LL tmp=r[i-j]*anss;
r[i]+=tmp;
}
r[i]/=i-1;
}
for(int i=1;i<=100;++i) {
u[i]=r[i]*2;
for(int j=1;j<i;++j) u[i]-=r[j]*r[i-j];
if(!(i&1)) u[i]-=r[i>>1];
u[i]/=2;
}
scanf("%d",&T);
while(T--) {
n=read();
LL tmpn=n;
if(n==1) puts("0");
else if(n>=2&&n<=5) puts("-1");
else if(n==6) puts("9");
else if(n==0) puts("155132763");
else {
LL ans=0;
for(int i=1;i<=100;++i) {
LL tmpi=i;
if(tmpn>=(tmpi*u[i])) tmpn-=(tmpi*u[i]),ans+=u[i];
else {
ans+=(tmpn/i);
break;
}
}
write(((ans+n*(n-3)/2)%mod+mod)%mod);
}
}
return 0;
}