不秃头的程序员

用户名：Liao123

访问量：3135

签　名：

等　　级
排　　名	7588
经　　验	1299
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2018年第九届真题-堆的计数-题解（Java代码）
浏览：682

蓝桥杯2018年第九届真题-缩位求和-题解（Java代码）
浏览：557

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

蓝桥杯2018年第九届真题-堆的计数-题解（Java代码）

　　作者: 不秃头的程序员　　　　发表时间：2020-10-06 20:16:24 浏览：682　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-堆的计数

```
import java.util.Scanner;

public class Main{
	private static final int MOD = 1000000009;
	private static int N;
	private static int[] size;	//记录每个节点的size
	private static long[] jie;	//记录1~N的阶乘
	private static long[] ni;	//记录1~N的阶乘的逆元
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		size = new int[N + 1];
		jie = new long[N + 1];
		ni = new long[N + 1];
		initSize();
		initJie();
		System.out.println(dp());
		
		sc.close();
	}
	private static long dp() {
		long[] d = new long[N + 1];	//d[i]表示的是i号节点作为根,小根堆的种数
		for(int x = N; x >= 1; x--) {
			if(2 * x + 1 <= N) {
				d[x] = c(size[x] - 1, size[2 * x]) * d[2 * x] % MOD * d[2 * x + 1] % MOD;
			}else if(2 * x <= N) {
				d[x] = c(size[x] - 1, size[2 * x]) * d[2 * x] % MOD;
			}else {
				d[x] = 1;
			}
		}
		return d[1];
	}
	private static void initJie() {
		jie[0] = 1;
		ni[0] = 1;
		for(int i = 1; i <= N; i++) {
			jie[i] = jie[i - 1] * i % MOD;
			ni[i] = qpow(jie[i], MOD - 2);
		}
	}
	private static long qpow(long a, int n) {
		if(a == 0) {
			return 0;
		}
		long ans = 1;
		long x = a;
		while(n > 0) {
			if((n & 1) == 1) {
				ans = ans * x % MOD;
			}
			n >>= 1;
			x = x * x % MOD;
		}
		return ans;
	}
	private static void initSize() {
		for(int i = N; i >= 1; i--) {
			size[i] = (2 * i <= N ? size[2 * i] : 0) + (2 * i + 1 <= N ? size[2 * i + 1] : 0) + 1;
		}
	}
	private static long c(int n, int r) {
		return jie[n] * ni[r] % MOD * ni[n-r] % MOD;
	}
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

不秃头的程序员

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C二级辅导-阶乘数列（C语言代码）

【计算直线的交点数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

转化为字符数组

蓝桥杯2018年第九届真题-堆的计数-题解（Java代码）

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

【金明的预算方案】（C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

IP判断（C语言代码）

C二级辅导-同因查找（C语言代码）

陶陶摘苹果2 （C语言代码）

母牛的故事（C语言代码）

不秃头的程序员

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

【计算直线的交点数】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

转化为字符数组

蓝桥杯2018年第九届真题-堆的计数-题解（Java代码）

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

【金明的预算方案】 （C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

IP判断 （C语言代码）

C二级辅导-同因查找 （C语言代码）

陶陶摘苹果2 （C语言代码）

母牛的故事 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

【计算直线的交点数】（C语言代码）

　　评论区

【金明的预算方案】（C++代码）

IP判断（C语言代码）

C二级辅导-同因查找（C语言代码）

母牛的故事（C语言代码）