二叉堆题解（分块打表）

题目大意

二叉堆是一种特殊的堆，其同时满足完全二叉树和堆的性质。

求有多少种不同的$n$个点的二叉堆满足所有节点的权值都在$1$到$n$之间且互不相同。输出答案对109+710^9+7109+7取模。

数据范围

1≤n≤1091\\leq n\\leq 10^91≤n≤109

题解

设sis_isi​表示子树$i$的大小，lil_ili​和rir_iri​分别表示$i$的左儿子和右儿子。

用$gt(i)$表示以$i$为根的子树内不重复地填上$1$到sis_isi​的方案数。则有

gt(i)=Csi−1sligt(li)×gt(ri)gt(i)=C_{s_i-1}^{s_{l_i}}gt(l_i)\\times gt(r_i)gt(i)=Csi​−1sli​​​gt(li​)×gt(ri​)

把组合数拆开后，经过整理，我们可以发现答案就是n!∏i=1nsi\\dfrac{n!}{\\prod\\limits_{i=1}^ns_i}i=1∏n​si​n!​。那么，可以先求1∏i=1nsi\\dfrac{1}{\\prod\\limits_{i=1}^ns_i}i=1∏n​si​1​，然后再乘上$n!$。

对于一棵完全二叉树，根节点的左右子树中至少有一棵为满二叉树。

令fif_ifi​表示子树大小为2i−12^i-12i−1的点的$s$值之积，那么有

fi=fi−1×fi−12i−1f_i=\\dfrac{f_{i-1}\\times f_{i-1}}{2^i-1}fi​=2i−1fi−1​×fi−1​​

那么，我们可以从根节点开始，先找到是满二叉树的子树，乘上它的贡献，然后递归到另一个子树中继续求值。

这样我们就可以$O(\log n)$求出1∏i=1nsi\\dfrac{1}{\\prod\\limits_{i=1}^ns_i}i=1∏n​si​1​。

那么，怎么求$n!$呢？分段打表即可。设分了$k$段，那么可以$O(1)$得出⌊n−1k⌋+1\\lfloor\\dfrac{n-1}{k}\\rfloor+1⌊kn−1​⌋+1的阶乘，然后O(109k)O(\\dfrac{10^9}{k})O(k109​)求出$n$的阶乘。

时间复杂度为O(log⁡n+109k)O(\\log n+\\dfrac{10^9}{k})O(logn+k109​)。

code

#include<bits/stdc++.h>
using namespace std;
long long ans,f[35];
long long t[100]={1,924724006,582347126,500419162,881147799,693776109,435873621,279027658,727951124,398578768,678364145,204828554,345795998,116118093,359401113,236930793,856493327,207383191,617606889,933753281,26701748,329394893,360779992,416008308,187501984,165706817,328891607,16385287,117411011,404196042,765064133,239669664,761588352,566114869,673499119,840260100,352356536,53839501,178657924,373444237,227300165,207172723,444208499,367531373,297449176,605324209,729265513,567907756,125889461,250743107,666666670,598576559,632705086,295855233,185718228,414607857,737215408,863388390,182290465,707552496,881713600,417895708,490627919,364521407,775935292,972492338,473340273,920880265,530581,696910290,64037482,649527920,756691728,283805222,711255329,825205499,263679166,341083474,914727729,919247968,465317279,960145703,274813468,393588827,65909169,521964827,794328994,484551338,521297378,54488990,591837535,255746228,25827429,177799409,92011129,469664591,35708489,197025781,288851931,254032854};
long long mod=1000000007;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
long long gt(int n){int x;long long re;for(x=1;(1<<x)-1<n;x++);if((1<<x)-1==n) return f[x];if(n<=(1<<x)-1-(1<<x-2)) re=f[x-2]*gt(n-(1<<x-2))%mod;else re=f[x-1]*gt(n-(1<<x-1))%mod;re=re*mi(n,mod-2)%mod;return re;
}
int main()
{int n;scanf("%d",&n);f[0]=1;for(int i=1;i<=30;i++) f[i]=f[i-1]*f[i-1]%mod*mi((1<<i)-1,mod-2)%mod;ans=gt(n)*t[(n-1)/10000000]%mod;for(int i=(n-1)/10000000*10000000+2;i<=n;i++) ans=ans*i%mod;printf("%lld",ans);return 0;
}