[BZOJ 3451] Normal

Posted on | In , | Views:

题目链接

BZOJ 3451

做法

其实我们要求的就是每个点在点分树上子树大小的和的期望。
很自然的会想到去计算每个点的贡献，而这道题最巧妙的地方在于，它计算的是点对的贡献。
考虑点$j$什么时候会出现在点$i$的点分树中。可以发现当点$i$是$i$到$j$这条链上第一个被选的点时，$j$会出现在$i$的点分树子树中，而这个概率显然是$\frac{1}{dis(i,j)}$。这里我们记$dis(i,j)$表示$i$到$j$这条链上的点数。
那么我们只要求出长度为$1..n$的链分别有多少条就行了。
可以用点分治$+FFT$解决。发现题目非常的良心，$n\le 30000$，也就是说每种长度的链不会很大，一定$<998244353$，所以我们就假设模数为$998244353$，就可以用$NTT$代替$FFT$了。

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (30005)
using namespace std;
int n,x,y,tot,root,totsize,invG,invL,lim,t1,t2;
int son[N<<1],nxt[N<<1],head[N],size[N],ans[N],dis[N],now[N<<1],f[N<<1],R[N<<1],g[N<<1],maxx[N],gg1[N],gg2[N],f1[N<<1],f2[N<<1]; 
bool vis[N];
const int P=998244353;
double res;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline void add(int x,int y){
    son[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
inline void getroot(int u,int fa){
    size[u]=1;
    maxx[u]=0;
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (v!=fa&&!vis[v]){
            getroot(v,u);
            size[u]+=size[v];
            maxx[u]=max(maxx[u],size[v]);
        }
    }
    maxx[u]=max(maxx[u],totsize-size[u]);
    if (maxx[u]<maxx[root]) root=u;
}
void dfs(int u,int fa){    
    now[dis[u]]++;
    gg1[++t1]=dis[u];
    gg2[++t2]=dis[u];
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (v!=fa&&!vis[v]){
            dis[v]=dis[u]+1;
            dfs(v,u);
        }        
    }
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
inline void NTT(int *f,int G){
    for (int i=0;i<lim;i++){
        if (i>R[i]) swap(f[i],f[R[i]]); 
    }
    for (int i=1;i<lim;i<<=1){
        int w0=ksm(G,(P-1)/(i<<1));
        for (int j=0;j<lim;j+=(i<<1)){
            int w=1;
            for (int k=j;k<j+i;k++){
                int t=1ll*w*f[k+i]%P;
                f[k+i]=Inc(f[k],P-t);
                f[k]=Inc(f[k],t);
                w=1ll*w*w0%P;
            }
        }
    }
    if (G!=3){
        for (int i=0;i<lim;i++) f[i]=1ll*f[i]*invL%P;
    }
}
inline void get(int x){
    for (lim=1;lim<=x;lim<<=1);    
    for (int i=0;i<lim;i++) R[i]=(R[i>>1]>>1)|((i&1)*lim>>1);
    invL=ksm(lim,P-2);
}
void solve(int u){
    t2=0;
    get(totsize); 
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (!vis[v]){
            t1=0;
            dis[v]=1;
            dfs(v,u);
            memset(f1,0,lim<<2);
            memset(f2,0,lim<<2);
            memcpy(f1,f,(totsize+1)<<2);
            memcpy(f2,now,(totsize+1)<<2);
            NTT(f1,3); 
            NTT(f2,3);
            for (int i=0;i<lim;i++) g[i]=1ll*f1[i]*f2[i]%P;
            NTT(g,invG);
            for (int i=0;i<=totsize;i++) ans[i]+=g[i];
            for (int i=0;i<=totsize;i++) f[i]+=now[i];  
            for (int i=1;i<=t1;i++) now[gg1[i]]=0;
        }
    }
    for (int i=1;i<=t2;i++) f[gg2[i]]=0;
    vis[u]=1;
    int tt=totsize;
    for (int p=head[u];p;p=nxt[p]){
        int v=son[p];
        if (!vis[v]){
            if (size[v]>size[u]) totsize=tt-size[u];
            else totsize=size[v];
            root=0;
            getroot(v,0);
            solve(root);
        }
    }
}
int main(){
    read(n);
    invG=ksm(3,P-2);
    for (int i=1;i<n;i++){
        read(x),read(y);
        x++,y++;
        add(x,y),add(y,x);
    }
    maxx[0]=1e9;
    root=0;
    totsize=n;
    f[0]=1;
    getroot(1,0);
    solve(root);
    for (int i=1;i<=n;i++){
        res+=1.0*ans[i]/(1+i);
    }
    printf("%.4lf",res*2+n);
    return 0;
}