无标号有根树/无根树 计数

当然是从有根树开始啦

树计数容易想到递归进行，设$n$个节点有根树的$\text{OGF}$为$F(x)$

我们考虑$F(x)$作为新根节点的子树的情况，这是一个可置换的背包问题，被称为$\text{Euler}$变换

不妨对于$F(x)$的每一项考虑，我们从$F_k$这么多种类的数中选择一些出来，然后组成背包

设$I=x^k$，$n=F_k$，那么对于这一项的变换可以表示为

$\displaystyle T(I,n)=\sum_{i=0}\binom{n} {i} (\sum_{j=1}^{\infty}I^j)^i=(\sum_{j=1}^{\infty}I^j+1)^n=\frac{1} {(1-I)^n}$

那么得到$\text{Euler}$变换

$\displaystyle \mathcal{E}(F(x))=\prod_{i=1}T(x^i,F_i)=\prod \frac{1} {(1-x^i)^{F_i} }$

两边求$\ln $

$\displaystyle \ln \mathcal{E}(F(x))=\sum_i F_i\ln \frac{1} {(1-x^i)}$

$\displaystyle \ln \mathcal{E}(F(x))=\sum_i F_i(\sum_{j=1}\frac{x^{ij} } {j})$

换循环

$\displaystyle \ln \mathcal{E}(F(x))=\sum_i \frac{1} {i}(\sum_{j=1}F_j(x^i)^j)=\sum \frac{F(x^i)} {i}$

$\displaystyle \mathcal{E}(F(x))=\text{exp}(\sum \frac{F(x^i)} {i})$

到这里我们得到了一个比较阳间的变换形式，那么$F(x)$的递归表示就是

$F(x)=x\cdot \mathcal{E}(F(x))$

考虑用牛顿迭代求解，设已经求出$G(x)=F(x)\mod x^n$，我们要求$F(x)\mod x^{2n}$

而$\displaystyle \mathcal{E}(F(x))=\text{exp}(\sum \frac{F(x^i)} {i})$中$i\ge 2$的项都是已知的，可以在$O(n\ln n)$时间得到，不妨这些项为常数$\text{coef}$

则方程为$x\cdot \text{exp}(F(x)+\text{coef})-F(x)=0$

方程函数为$f(z)=xe^{z+\text{coef} }-z$

$f’(z)=xe^{z+\text{coef} }-1$

故知$\displaystyle F(x)=G(x)-\frac{xe^{G(x)+\text{coef} }-G(x)} {xe^{G(x)+\text{coef} }-1}$

(这里没有分治解法的。。。实际我也不会)

下面是无根树计数，考虑令重心为根即可

可以直接减掉存在一个子树$> \frac{n} {2}$的贡献，因为不会出现置换重复，可以将这个子树从原来的树上踢掉

剩下部分依然看成一棵有根树，也就是$F_i\cdot F_{n-i}(i>\frac{n} {2})$

对于$2|n$的情况，重心可能有两个，此时要减去对称情况$\displaystyle \binom{F_{\frac{n} {2} }} {2}$

Luogu P5900 Submission

唔-好慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
typedef vector <int> V;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int L=19,N=1<<L|10,P=998244353;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];
int rev[N],w[N];
void Init(){
	w[1<<(L-1)]=1;
	int t=qpow(3,(P-1)>>L);
	rep(i,(1<<(L-1))+1,1<<L) w[i]=1ll*w[i-1]*t%P;
	drep(i,(1<<(L-1))-1,1) w[i]=w[i<<1];
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &A,int f) {
	static ull a[N];
	if((int)A.size()<n) A.resize(n);
	rep(i,0,n-1) a[rev[i]]=A[i];
	for(int i=1;i<n;i<<=1) {
		int *e=w+i;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=a[j+i]*e[j-l]%P;
				a[j+i]=a[j]+P-t;
				a[j]+=t;
			}
		}
	}
	rep(i,0,n-1) A[i]=a[i]%P,Mod2(A[i]);
	if(f==-1) {
		reverse(A.begin()+1,A.end());
		ll base=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) A[i]=A[i]*base%P;
	}
}

V operator + (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
V operator * (V a,V b) {
	int n=a.size()-1,m=b.size()-1;
	int R=Init(n+m);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1),a.resize(n+m+1);
	return a;
}
V operator * (V a,const int &x) {
	for(int &i:a) i=1ll*i*x%P;
	return a;
}
V operator * (const int &x,V a) { return a*x; }

void println(const V &a){
	for(int i:a) printf("%d ",i);
	puts("");
}
V read(int n){
	V A(n);
	rep(i,0,n-1) A[i]=rd();
	return A;
}
V operator ~ (V a) {
	int n=a.size(),m=(n+1)>>1;
	if(n==1) return assert(a[0]),V{(int)qpow(a[0])};
	V b=a; b.resize(m),b=~b;
	int R=Init(n*2);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=(P+2-1ll*a[i]*b[i]%P)*b[i]%P;
	NTT(R,a,-1),a.resize(n);
	return a;
}
V Deriv(V a) {
	rep(i,0,a.size()-2) a[i]=1ll*(i+1)*a[i+1]%P;
	a.pop_back();
	return a;
}
V Integ(V a){
	a.pb(0);
	drep(i,a.size()-1,1) a[i]=1ll*a[i-1]*J[i-1]%P*I[i]%P;
	a[0]=0;
	return a;
}
V Ln(V a){
	int n=a.size();
	a=Deriv(a)*~a;
	return a.resize(n-1),Integ(a);
}
V Exp(V a) {
	if(a.size()==1) return assert(a[0]==0),V{1};
	int n=a.size();
	V b=a; b.resize((n+1)/2),b=Exp(b),b.resize(n);
	a=a-Ln(b),a[0]++;
	a=a*b,a.resize(n);
	return a;
}

V operator << (V a,int x) {
	a.resize(a.size()+x);
	drep(i,a.size()-1,x) a[i]=a[i-x];
	rep(i,0,x-1) a[i]=0;
	return a;
}
V operator >> (V a,int x) {
	if((int)a.size()<=x) return V{ };
	rep(i,x,a.size()-1) a[i-x]=a[i];
	a.resize(a.size()-x);
	return a;
}

V Newton(int n){
	if(n==1) return V{0};
	if(n==2) return V{0,1};
	V G=Newton((n+1)/2); G.resize(n);
	V T=G;
	rep(i,2,n-1) {
		int t=1ll*I[i]*J[i-1]%P;
		rep(j,1,min(n/2,(n-1)/i)) T[i*j]=(T[i*j]+1ll*G[j]*t)%P;
	}
	T=Exp(T)<<1;
	V F=G-(T-G)*~(T-V{1});
	return F.resize(n),F;
}

int main(){
	int n=rd()+1; Init();
	V F=Newton(n); 
	int ans=F[--n];
	rep(i,1,(n-1)/2) ans=(ans-1ll*F[i]*F[n-i])%P;
	if(~n&1) ans=(ans-1ll*F[n/2]*(F[n/2]-1)/2)%P;
	Mod2(ans);
	printf("%d\n",ans);
}