题面

512mb, 4s

$1\le n\le 10^5,0\le K\le 10,1\le u,v\le n$ 。

题解

我们首先有这个公式：
$$\varphi (xy)=\varphi (x)\varphi (y)\cdot \frac{gcd(x,y)}{\varphi (gcd(x,y))}$$

那么就可以代入答案
$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^n\varphi (ij)d^k(i,j)=\sum _{i=1}^n\sum _{j=1}^n\varphi (i)\varphi (j)\frac{gcd(i,j)}{\varphi (gcd(i,j))}{d}^k(i,j) \\ =\sum _{g=1}^n\frac{g}{\varphi (g)}\sum _{i=1}^n\sum _{j=1}^n\varphi (i)\varphi (j)[gcd(i,j)=g]d^k(i,j) \end{gathered}$$

这一步我们用个莫反：
$$\begin{gathered} =\sum _{g=1}^n\frac{g}{\varphi (g)}\sum _{g|T}\mu (T/g)\sum _{T|i}^n\sum _{T|j}^n\varphi (i)\varphi (j)d^k(i,j) \\ =\sum _{T=1}^n\left(\sum _{T|i}^n\sum _{T|j}^n\varphi (i)\varphi (j)d^k(i,j)\right)\left(\sum _{g|T}\frac{g}{\varphi (g)}\mu (T/g)\right) \end{gathered}$$

然后我们就可以预处理右边那一坨。

暴力枚举 $T$ 的倍数总共有 $O(n\ln n)$ 个。我们对于每个 $T$ ，拿出所有 $T$ 的倍数，建立虚树。

两个点 $A,B$ 在 $lca$ 处产生贡献，假设左边部分长度为 $a$ ，右边部分长度为 $b$ ，怎么将两者合并？

我们考虑将 $k=0\sim K$ 的情况放进 $EGF$ 里，具体的，
$$F_A=\sum _{i=0}^K\varphi (A)a^i\cdot \frac{x^i}{i!},F_B=\sum _{i=0}^K\varphi (B)b^i\cdot \frac{x^i}{i!}$$

把 $F_A,F_B$ 相乘，卷积起来就可以得到 $k=0\sim K$ 的 $\varphi (i)\varphi (j)d^k(i,j)$ 。

所以，我们对虚树进行 $\mathrm{d}\mathrm{f}\mathrm{s}$ ，处理出每个子树到达各个后代的 $EGF$ 的和，合并两个子树的贡献直接将 $EGF$ 乘起来就好了。

将 $A$ 的 $EGF$ 从 $a^k$ 扩展到 $(a+1{)}^k$ 可以卷上一个 $\sum \frac{x^i}{i!}$ 。

时间复杂度 $O(n\ln n(\log n+K^2))$ 。

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
#define getchar() xchar()
inline LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 998244353;
int n,m,s,o,k;
inline void MD(int &x) {if(x>=MOD)x-=MOD;}
int inv[MAXN],fac[MAXN],invf[MAXN];
vector<int> fc[MAXN];
int p[MAXN],cnt,f[MAXN],mu[MAXN],F[MAXN],dv[MAXN],phi[MAXN];
void init(int n) {
	inv[0] = inv[1] = 1;
	for(int i = 2;i <= max(n,15);i ++) inv[i] = (MOD-inv[MOD%i]) *1ll* (MOD/i) % MOD;
	fac[0] = invf[0] = 1;
	for(int i = 1;i <= 15;i ++) {
		fac[i] = fac[i-1] *1ll* i % MOD;
		invf[i] = invf[i-1] *1ll* inv[i] % MOD;
	}
	f[1] = 1; cnt = 0; mu[1] = 1; dv[1] = 1; phi[1] = 1;
	for(int i = 2;i <= n;i ++) {
		if(!f[i]) {
			p[++ cnt] = i;
			mu[i] = -1;phi[i] = i-1;dv[i] = i*1ll*inv[i-1]%MOD;
		}
		for(int j = 1,nm;j <= cnt && (nm=i*p[j]) <= n;j ++) {
			f[nm] = 1;
			if(i % p[j] == 0) {
				mu[nm] = 0; phi[nm] = phi[i]*p[j];
				dv[nm] = dv[i]; break;
			}
			mu[nm] = -mu[i]; phi[nm] = phi[i]*phi[p[j]];
			dv[nm] = dv[i] *1ll* dv[p[j]] % MOD;
		}
	}
	for(int i = 1;i <= n;i ++) {
		for(int j = i,k = 1;j <= n;j += i,k ++) {
			fc[j].push_back(i);
			MD(F[j] += (MOD+mu[i])*1ll*dv[k]%MOD);
		}
	} return ;
}
int a[MAXN],dfn[MAXN],tim;
inline bool cmp(int a,int b) {return dfn[a] < dfn[b];}
vector<int> g[MAXN];
int d[MAXN],fa[MAXN][20];//17
void dfs0(int x,int ff) {
	d[x] = d[fa[x][0] = ff] + 1; dfn[x] = ++ tim;
	for(int i = 1;i <= 17;i ++) fa[x][i] = fa[fa[x][i-1]][i-1];
	for(int y:g[x]) if(y != ff) dfs0(y,x);
	return ;
}
int lca(int a,int b) {
	if(d[a] < d[b]) swap(a,b);
	if(d[a] > d[b]) for(int i = 17;i >= 0;i --) {
		if(d[fa[a][i]] >= d[b]) a = fa[a][i];
	} if(a == b) return a;
	for(int i = 17;i >= 0;i --) {
		if(fa[a][i] ^ fa[b][i]) {
			a = fa[a][i]; b = fa[b][i];
		}
	} return fa[a][0];
}
int tg[MAXN],wt[MAXN];
int hd[MAXN],nx[MAXN<<1],v[MAXN<<1],w[MAXN<<1],cne;
void ins(int x,int y,int z) {
	nx[++cne] = hd[x]; v[cne] = y; hd[x] = cne; w[cne] = z;
}
struct vec{
	int s[11];
	vec(){memset(s,0,sizeof(s));}
	vec(int d) {
		for(int i = 0,p = 1;i <= m;i ++,p = p*1ll*d%MOD)
			s[i] = p*1ll*invf[i] % MOD;
	}
}dp[MAXN];
inline vec operator * (vec a,vec b) {
	for(int i = m;i >= 0;i --) {
		int nm = 0;
		for(int j = 0;j <= i;j ++) {
			nm = (nm + a.s[i-j]*1ll*b.s[j]) % MOD;
		} a.s[i] = nm;
	} return a;
}
inline vec& operator *= (vec &a,vec b) {
	for(int i = m;i >= 0;i --) {
		int nm = 0;
		for(int j = 0;j <= i;j ++) {
			nm = (nm + a.s[i-j]*1ll*b.s[j]) % MOD;
		} a.s[i] = nm;
	} return a;
}
inline vec& operator += (vec &a,vec b) {
	for(int i = 0;i <= m;i ++) {
		MD(a.s[i] += b.s[i]);
	} return a;
}
vec as;
void dfs(int x,int ff) {
	dp[x] = vec(); MD(dp[x].s[0] += wt[x]);
	MD(as.s[0] += wt[x]*1ll*wt[x]%MOD*inv[2]%MOD);
	for(int i = hd[x];i;i = nx[i]) {
		int y = v[i]; if(y == ff) continue;
		dfs(y,x); dp[y] *= vec(w[i]);
		as += dp[x] * dp[y];
		for(int j = 0;j <= m;j ++) MD(dp[x].s[j] += dp[y].s[j]);
	}
	return ;
}
int st[MAXN],tp;
int main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n = read(); m = read();
	init(n);
	for(int i = 1;i < n;i ++) {
		s = read();o = read();
		g[s].push_back(o);
		g[o].push_back(s);
	}
	dfs0(1,0);
	vec ans;
	for(int D = 1;D <= n;D ++) {
		int cn = 0; cne = 0;
		for(int j = D;j <= n;j += D) {
			a[++ cn] = j; wt[j] = phi[j];
			tg[j] = D; hd[j] = 0;
		}
		sort(a + 1,a + 1 + cn,cmp);
		st[tp = 1] = a[1];
		for(int i = 1;i <= cn;i ++) {
			int x = a[i],lc = lca(x,st[tp]),p = 0;
			if(tg[lc] != D) {
				tg[lc] = D; wt[lc] = hd[lc] = 0;
			}
			while(tp > 0 && d[st[tp]] > d[lc]) {
				if(p) ins(st[tp],p,d[p]-d[st[tp]]);
				p = st[tp --];
			}
			if(p) ins(lc,p,d[p] - d[lc]);
			if(st[tp] != lc) st[++ tp] = lc;
			if(x != lc) st[++ tp] = x;
		}
		int p = 0;
		while(tp > 0) {
			if(p) ins(st[tp],p,d[p]-d[st[tp]]);
			p = st[tp --];
		}
		as = vec();
		dfs(p,0);
		for(int i = 0;i <= m;i ++) as.s[i] = as.s[i] *2ll* F[D] % MOD;
		ans += as;
	}
	for(int i = 0;i <= m;i ++) {
		AIput(ans.s[i]*1ll*fac[i]%MOD,'\n');
	}
	return 0;
}
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202