当前位置:网站首页>【NOI模拟赛】Anaid 的树(莫比乌斯反演,指数型生成函数,埃氏筛,虚树)
【NOI模拟赛】Anaid 的树(莫比乌斯反演,指数型生成函数,埃氏筛,虚树)
2022-07-05 23:52:00 【DD(XYX)】
题面
512mb, 4s
1 ≤ n ≤ 1 0 5 , 0 ≤ K ≤ 10 , 1 ≤ u , v ≤ n 1\leq n\leq 10^5,0\leq K\leq 10,1\leq u,v\leq n 1≤n≤105,0≤K≤10,1≤u,v≤n 。
题解
我们首先有这个公式:
ϕ ( x y ) = ϕ ( x ) ϕ ( y ) ⋅ g c d ( x , y ) ϕ ( g c d ( x , y ) ) \phi(xy)=\phi(x)\phi(y)\cdot \frac{gcd(x,y)}{\phi(gcd(x,y))} ϕ(xy)=ϕ(x)ϕ(y)⋅ϕ(gcd(x,y))gcd(x,y)
那么就可以代入答案
∑ i = 1 n ∑ j = 1 n ϕ ( i j ) d k ( i , j ) = ∑ i = 1 n ∑ j = 1 n ϕ ( i ) ϕ ( j ) g c d ( i , j ) ϕ ( g c d ( i , j ) ) d k ( i , j ) = ∑ g = 1 n g ϕ ( g ) ∑ i = 1 n ∑ j = 1 n ϕ ( i ) ϕ ( j ) [ g c d ( i , j ) = g ] d k ( i , j ) \sum_{i=1}^n\sum_{j=1}^n\phi(ij)d^k(i,j)=\sum_{i=1}^n\sum_{j=1}^n\phi(i)\phi(j)\frac{gcd(i,j)}{\phi(gcd(i,j))}d^k(i,j)\\ =\sum_{g=1}^n\frac{g}{\phi(g)}\sum_{i=1}^n\sum_{j=1}^n\phi(i)\phi(j)[gcd(i,j)=g]d^k(i,j)\\ i=1∑nj=1∑nϕ(ij)dk(i,j)=i=1∑nj=1∑nϕ(i)ϕ(j)ϕ(gcd(i,j))gcd(i,j)dk(i,j)=g=1∑nϕ(g)gi=1∑nj=1∑nϕ(i)ϕ(j)[gcd(i,j)=g]dk(i,j)
这一步我们用个莫反:
= ∑ g = 1 n g ϕ ( g ) ∑ g ∣ T μ ( T / g ) ∑ T ∣ i n ∑ T ∣ j n ϕ ( i ) ϕ ( j ) d k ( i , j ) = ∑ T = 1 n ( ∑ T ∣ i n ∑ T ∣ j n ϕ ( i ) ϕ ( j ) d k ( i , j ) ) ( ∑ g ∣ T g ϕ ( g ) μ ( T / g ) ) =\sum_{g=1}^n\frac{g}{\phi(g)}\sum_{g|T}\mu(T/g)\sum_{T|i}^n\sum_{T|j}^n\phi(i)\phi(j)d^k(i,j)\\ =\sum_{T=1}^n\left(\sum_{T|i}^n\sum_{T|j}^n\phi(i)\phi(j)d^k(i,j)\right)\left(\sum_{g|T}\frac{g}{\phi(g)}\mu(T/g)\right) =g=1∑nϕ(g)gg∣T∑μ(T/g)T∣i∑nT∣j∑nϕ(i)ϕ(j)dk(i,j)=T=1∑n⎝⎛T∣i∑nT∣j∑nϕ(i)ϕ(j)dk(i,j)⎠⎞⎝⎛g∣T∑ϕ(g)gμ(T/g)⎠⎞
然后我们就可以预处理右边那一坨。
暴力枚举 T T T 的倍数总共有 O ( n ln n ) O(n\ln n) O(nlnn) 个。我们对于每个 T T T ,拿出所有 T T T 的倍数,建立虚树。
两个点 A , B A,B A,B 在 l c a lca lca 处产生贡献,假设左边部分长度为 a a a ,右边部分长度为 b b b ,怎么将两者合并?
我们考虑将 k = 0 ∼ K k=0\sim K k=0∼K 的情况放进 E G F EGF EGF 里,具体的,
F A = ∑ i = 0 K ϕ ( A ) a i ⋅ x i i ! , F B = ∑ i = 0 K ϕ ( B ) b i ⋅ x i i ! F_{A}=\sum_{i=0}^K \phi(A)a^i\cdot\frac{x^i}{i!},F_B=\sum_{i=0}^K\phi(B)b^i\cdot\frac{x^i}{i!} FA=i=0∑Kϕ(A)ai⋅i!xi,FB=i=0∑Kϕ(B)bi⋅i!xi
把 F A , F B F_A,F_B FA,FB 相乘,卷积起来就可以得到 k = 0 ∼ K k=0\sim K k=0∼K 的 ϕ ( i ) ϕ ( j ) d k ( i , j ) \phi(i)\phi(j)d^k(i,j) ϕ(i)ϕ(j)dk(i,j) 。
所以,我们对虚树进行 d f s \rm dfs dfs ,处理出每个子树到达各个后代的 E G F EGF EGF 的和,合并两个子树的贡献直接将 E G F EGF EGF 乘起来就好了。
将 A A A 的 E G F EGF EGF 从 a k a^k ak 扩展到 ( a + 1 ) k (a+1)^k (a+1)k 可以卷上一个 ∑ x i i ! \sum \frac{x^i}{i!} ∑i!xi 。
时间复杂度 O ( n ln n ( log n + K 2 ) ) O(n\ln n(\log n+K^2)) O(nlnn(logn+K2)) 。
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;
}
边栏推荐
- QCombox(重写)+QCompleter(自动补全,自动加载qcombox的下拉选项,设置背景颜色)
- Russian Foreign Ministry: Japan and South Korea's participation in the NATO summit affects security and stability in Asia
- Bao Yan notes II software engineering and calculation volume II (Chapter 13-16)
- [SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)
- 如何让同步/刷新的图标(el-icon-refresh)旋转起来
- Redis high availability - master-slave replication, sentinel mode, cluster
- CAS and synchronized knowledge
- GD32F4xx uIP协议栈移植记录
- Make a short video clip number of we media film and television. Where can I download the material?
- Add noise randomly to open3d point cloud
猜你喜欢
随机推荐
Rasa 3. X learning series -rasa 3.2.1 new release
20.移植Freetype字体库
如何提升口才
[online chat] the original wechat applet can also reply to Facebook homepage messages!
什么叫做信息安全?包含哪些内容?与网络安全有什么区别?
What are the functions of Yunna fixed assets management system?
GFS distributed file system
5. Logistic regression
orgchart. JS organization chart, presenting structural data in an elegant way
Cwaitabletimer timer, used to create timer object access
STM32__06—单通道ADC
Fiddler Everywhere 3.2.1 Crack
【luogu P3295】萌萌哒(并查集)(倍增)
MySQL replace primary key delete primary key add primary key
QT QPushButton details
Problem solving win10 quickly open ipynb file
如何获取localStorage中存储的所有值
CAS and synchronized knowledge
QT--线程
Go language introduction detailed tutorial (I): go language in the era