題目描述

Problem description.
You are given a tree. If we select 2 distinct nodes uniformly at random, what’s the probability that the distance between these 2 nodes is a prime number?
Input
The first line contains a number N: the number of nodes in this tree.
The following N-1 lines contain pairs a[i] and b[i], which means there is an edge with length 1 between a[i] and b[i].
Output
Output a real number denote the probability we want.
You’ll get accept if the difference between your answer and standard answer is no more than 10^-6.
Constraints
2 ≤ N ≤ 50,000
The input must be a tree.
Example
Input:
5
1 2
2 3
3 4
4 5
Output:
0.5
Explanation
We have C(5, 2) = 10 choices, and these 5 of them have a prime distance:
1-3, 2-4, 3-5: 2
1-4, 2-5: 3
Note that 1 is not a prime number.

題目分析

使用樹分治后我們能夠得到任意點(diǎn)到重心的距離，現(xiàn)在問題轉(zhuǎn)換為如何判斷兩點(diǎn)之間的距離為素?cái)?shù)。

首先我們要使用線性篩處理出一個(gè)素?cái)?shù)表。

一個(gè)簡(jiǎn)單的想法是我們將Dis數(shù)組中不同的點(diǎn)加起來就是不同兩點(diǎn)之間的距離。然后再判斷這個(gè)距離是不是素?cái)?shù)，如果是素?cái)?shù)則將路徑+1。可是這樣時(shí)間復(fù)雜度太高（O(n*n)），因此我們需要使用FFT進(jìn)行加速，快速得到兩路徑的和。但是我們需要減去同一條路徑走兩邊的情況。

需要求概率，我們就需要知道事件數(shù)是什么。對(duì)于這里來講，我們需要考慮的是選擇排列還是組合。由給出的樣例我們看出，應(yīng)該按照組合進(jìn)行計(jì)算。因此對(duì)于每個(gè)路徑和我們都應(yīng)該/2，這樣得到的才是排列數(shù)。

需要注意的是每次FFT以后對(duì)數(shù)組的清零。我就是這里沒有注意然后導(dǎo)致瘋狂出錯(cuò)，還一直檢查不出問題。

還有就是，樹上的路徑很多，很容易爆long long

AC代碼

#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath>using namespace std;const int MAXN=5e5+5; const double PI=acos(-1.0); typedef long long ll; struct edge {int to,len,last; }Edge[MAXN<<2]; int Last[MAXN],tot; int n,kk,SonNum[MAXN],MaxNum[MAXN],Vis[MAXN],Dis[MAXN]; int Prime[MAXN]; bool IsPrime[MAXN]; int prime_num=0; int root,rootx,dlen,ss; ll Num[MAXN<<2],MaxLen,len; ll Res[MAXN<<2]; ll ans;struct complex {double r,i;complex(double _r=0,double _i=0):r(_r),i(_i){}complex operator +(const complex &b) {return complex(r+b.r,i+b.i);}complex operator -(const complex &b) {return complex(r-b.r,i-b.i);}complex operator *(const complex &b) {return complex(r*b.r-i*b.i,r*b.i+i*b.r);} }A[MAXN<<2];void change(complex y[],int len) {int i,j,k;for(i = 1, j = len/2;i < len-1;i++){if(i < j)swap(y[i],y[j]);k = len/2;while( j >= k){j -= k;k /= 2;}if(j < k)j += k;} }void fft(complex y[],int len,int on) {change(y,len);for(int h = 2;h <= len;h <<= 1){complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for(int j = 0;j < len;j += h){complex w(1,0);for(int k = j;k < j+h/2;k++){complex u = y[k];complex t = w*y[k+h/2];y[k] = u+t;y[k+h/2] = u-t;w = w*wn;}}}if(on == -1)for(int i = 0;i < len;i++)y[i].r /= len; }void FFT(ll a[],int la,ll b[])//la,lb分別是a,b數(shù)組的最高位+1 {//int len=1; while(len<la+la) len<<=1;for(int i=0;i<la;++i) A[i]=complex(a[i],0);for(int i=la;i<len;++i) A[i]=complex(0,0);fft(A,len,1);for(int i=0;i<len;++i) A[i]=A[i]*A[i];fft(A,len,-1);for(int i=0;i<len;++i) b[i]=(ll)(A[i].r+0.5); }void CreatPrime() {IsPrime[0]=IsPrime[1]=true; prime_num=0;for(int i=2;i<MAXN;++i){if(!IsPrime[i])Prime[prime_num++]=i;for(int j=0;j<prime_num && Prime[j]*i<MAXN;j++){IsPrime[Prime[j]*i]=true;if(i%Prime[j]==0) break;}} }int getint() {int x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0'; c=getchar();}return x*sign; }void Init() {//CreatPrime();//for(int i=0;i<=n;++i) Last[i]=0; memset(Last,-1,sizeof(Last));tot=0;ans=0; }void Clear() {for(int i=0;i<=n;++i) Vis[i]=false; }void AddEdge(int u,int v,int w) {Edge[++tot].to=v; Edge[tot].len=w; Edge[tot].last=Last[u]; Last[u]=tot; }void Read() {n=getint();int u,v;for(int i=1;i<n;i++){u=getint(); v=getint();AddEdge(u,v,1); AddEdge(v,u,1);} }void GetRoot(int x,int father) {int v;SonNum[x]=1; MaxNum[x]=1;for(int i=Last[x];~i;i=Edge[i].last){v=Edge[i].to; if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}if(ss-SonNum[x]>MaxNum[x]) MaxNum[x]=ss-SonNum[x];if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x]; }void GetDis(int x,int father,int dis) {int v;Dis[++dlen]=dis;for(int i=Last[x];~i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,dis+Edge[i].len);} }ll Count(int x,int dis) {ll ret=0;for(int i=0;i<=dlen;++i) Dis[i]=0;dlen=0;GetDis(x,0,dis);/*for(int i=1;i<=dlen;++i)for(int j=i+1;j<=dlen;++j){if(!IsPrime[Dis[i]+Dis[j]]) ++ret;}*///memset(Num,0,sizeof(Num));MaxLen=0;for(int i=1;i<=dlen;++i){++Num[Dis[i]]; if(Dis[i]>MaxLen) MaxLen=Dis[i];}len=1; while(len<=2*MaxLen) len<<=1;FFT(Num,MaxLen+1,Res);for(int i=1;i<=dlen;++i){--Res[Dis[i]+Dis[i]];}MaxLen<<=1;for(int i=0;i<=len;++i){Res[i]/=2;}for(int i=0;i<prime_num && Prime[i]<=MaxLen;++i){ret+=Res[Prime[i]];}for(int i=1;i<=dlen;++i){Num[Dis[i]]=0;}return ret; }void Solve(int x) {int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];~i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;ans-=Count(v,Edge[i].len);ss=SonNum[v]; rootx=INT_MAX; root=0;GetRoot(v,x);Solve(root);} }void Work() {rootx=INT_MAX; ss=n; root=0;GetRoot(1,0); Solve(root); }void Write() {ll tmp=(ll)n*(n-1)/2;//printf("%.f\n",tmp);printf("%.7f\n",(double)ans/tmp);}int main() {CreatPrime();//while(~scanf("%d",&n))//{Init();Read();Work();Write();Clear();//}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Prime Distance On Tree-树分治+FFT的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。