HDU-5279(CDQ+NTT)

本质其实是要求\(n\)个点森林数量\(dp_n\)，\(n\)个点森林并且\(1,n\)在同一连通块的数量\(f_n\)

总方案就是\(\Pi dp_{a_i}\cdot 2^n-\Pi f_{a_i}\)

就是减去所有环都连着，并且\(1,a_i\)连着的方案数

我们知道\(n\)个点树的数量是\(n^{n-2}\)(Prufer序列)

枚举\(1\)号点所在树的大小为\(j\)，则\(dp_i=dp_{i-j}\cdot j^{j-2}\cdot C(i-1,j-1)\)

可以看到是一个与差值有关的转移，可以通过\(CDQ+NTT\)优化

然后就是求\(f_i\)，其实就是枚举\(1,i\)号点所在树的大小为\(j\)，\(f_i=dp_{i-j}\cdot C(i-2,j-2) \cdot j^{j-2}\)，可以直接\(NTT\)解决

#include
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

template  inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template  inline void cmax(T &a,T b){ ((a>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
ll dp[N],f[N],A[N],B[N];
int rev[N];

void NTT(int n,ll *a,int f) {
	rep(i,0,n-1) if(rev[i]=P&&(a[j]-=P));
			}
		}
	}
	if(f==-1) {
		ll base=qpow(n,P-2);
		rep(i,0,n-1) a[i]=a[i]*base%P;
	}
}

void Solve(int l,int r) {  // CDQ计算dp
	if(l==r) return;
	int mid=(l+r)>>1;
	Solve(l,mid);
	int R=1,cc=-1;
	while(R<=r-l+1) R<<=1,cc++;
	rep(i,1,R) rev[i]=(rev[i>>1]>>1)|((i&1)<>1]>>1)|((i&1)<