3805. 【NOIP2014模拟8.24】小X 的二叉堆計數

Description

衆所周知，完全二叉樹是一種二叉樹，滿足除最後一層外的每層結點都是滿的，且最後一層的結點連續集中在左方。而二叉堆是一種完全二叉樹，分為大根堆和小根堆，大根堆滿足父結點的值不小于子結點的值，小根堆滿足父結點的值不大于子結點的值。

小X 最近對二叉堆和樹的計數都很感興趣，他想知道n 個互不相同的數能構成多少個不同的大小為n 的二叉堆，希望你幫幫他。

Input

第一行包含一個整數n。

Output

第一行包含一個整數，表示能構成的二叉堆個數模10^9 + 7。

Sample Input

3      

Sample Output

4      

Data Constraint

對于30% 的資料，n ≤ 10。

對于60% 的資料，n ≤ 1000。

對于80% 的資料，n ≤ 10^5。

對于100% 的資料，1 ≤ n ≤ 5 × 10^6。

Solution

第一眼還以為是斯特林數，但仔細一看其實不是。它的堆的形态已經确定，是以我們很容易可以得到遞推式

（其中l[i]表示左子樹的兒子個數，ri是是右子樹）

表示第一個對頂元素已經确定後，任意選擇li個數放到左子樹，剩下的數放到右子樹後，再乘上左子樹和右子樹的形态的方案數就是i的答案。

最後答案是f[n]*2，有大小根堆。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 5000010
#define M 1000000007
using namespace std;
void rd(ll &x){
	x=0;ll w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=w;
}
ll n,T[24],S[24],f[N],F[N],inv[N];
ll ksm(ll x,ll k){
	if(k==1) return x%M;
	ll st=ksm(x,k/2);st=(st*st)%M;
	if(k&1) return st*x%M;
	return st;
}
ll work(ll x){
	ll p=1,sum=0,left=0;
	while(S[p+1]<=x) p++;
	sum+=(S[p]-1)>>1;
	left=x-S[p];
	if(left>=T[p-1]) sum+=T[p-1];
	else sum+=left;
	return sum;
}
ll C(ll n,ll m){return f[n]*inv[m]%M*inv[n-m]%M;}
I main(){
	rd(n);
	if(n==1){
		printf("1\n");	
		return 0;
	}
	T[0]=f[0]=F[0]=F[1]=1;
	F(i,1,23) T[i]=T[i-1]*2;
	F(i,1,23) S[i]=S[i-1]+T[i-1];
	F(i,1,n) f[i]=(f[i-1]*(ll)i)%M;
	inv[n]=ksm(f[n],M-2);
	Fd(i,n-1,0) inv[i]=inv[i+1]*(ll)(i+1)%M;
	F(i,2,n){
		ll x=work(i);
		F[i]=C(i-1,x)*F[x]%M*F[i-x-1]%M;
	}
	printf("%lld\n",(F[n]*2)%M);
	return 0;
}