test20190417

Posted on | Views:

测试.

$heap$

  • 有多少个节点数目为 $n​$ ,权值为 $1\sim n​$ 且互不相同的二叉堆?答案对 $10^9+7​$ 取模.
  • $n\leq 10^9​$ .
  • $O(n)$ 的做法十分简单, 先搞出每个节点的 $siz$ ,记 $f(i)$ 表示子树 $i$ 内用 $siz_i$ 个权值能形成的合法二叉堆数目.
  • 转移显然有 $f(i)={siz_i\choose siz_{2i}}\cdot f(2i)\cdot f(2i+1)$ ,叶子节点 $f(i)=1$ .
  • 把组合数拆开,算算贡献,可以发现 $f(1)=\frac {n!} {\prod siz_i}$ .考虑 $siz$ 连乘积怎么算.
  • 注意到一个点的左右子树至少有一个是满的二叉树(每一层填满),那么就可以先求出每种满二叉树的答案,此时递归入另一个子树继续计算就可以了.这部分的时间复杂度为 $O(logn)​$ .
  • 还有一个 $n!​$ 需要计算.分块打下表,就能很快求出啦.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int inv(int x)
{
	return fpow(x,P-2);
}
int m=1000000;
int calcfac(int x)  
{
	int pos=x/m;
	int s=blockfac[pos];
	for(int i=pos*m+1;i<=x;++i)
		s=mul(s,i);
	return s;
}
int n;
map<int,int> mp;
int solve(int x)//x个点,x个互异权值,siz连乘积
{
	if(x<=1)
		return 1;
	if(mp.find(x)!=mp.end())
		return mp[x];
	int z=(int)(log2(x));
	z=1<<z;
	int y=min(z-1,x-z/2);
	return mp[x]=mul(x,mul(solve(y),solve(x-y-1)));
}
int main()
{
	freopen("heap.in","r",stdin);
	freopen("heap.out","w",stdout);
	n=read();
	cout<<mul(calcfac(n),(inv(solve(n))))<<endl;
	return 0;
}

这里用了另一种等价的做法,意义不是很明显?略去了表的数据.

$secret$

  • 待更.

$tree$

  • 待更.