蓝桥杯——标题：堆的计数

pengsay 2021-02-19 原文

import java.util.Scanner;

/**
 * @Author LZP
 * @Date 2021/1/23 18:50
 * @Version 1.0
 * <p>
 * <p>
 * 标题：堆的计数
 * <p>
 * 我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。
 * 每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。
 * <p>
 * 假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？
 * <p>
 * 例如对于N=4有如下3种：
 * <p>
 * 1
 * / \
 * 2   3
 * /
 * 4
 * <p>
 * 1
 * / \
 * 3   2
 * /
 * 4
 * <p>
 * 1
 * / \
 * 2   4
 * /
 * 3
 * <p>
 * 由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。
 * <p>
 * <p>
 * 【输入格式】
 * 一个整数N。
 * 对于40%的数据，1 <= N <= 1000
 * 对于70%的数据，1 <= N <= 10000
 * 对于100%的数据，1 <= N <= 100000
 * <p>
 * 【输出格式】
 * 一个整数表示答案。
 * <p>
 * 【输入样例】
 * 4
 * <p>
 * 【输出样例】
 * 3
 * <p>
 * <p>
 * 资源约定：
 * 峰值内存消耗（含虚拟机） < 256M
 * CPU消耗  < 1000ms
 * <p>
 * <p>
 * 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
 * <p>
 * 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
 * 不要使用package语句。不要使用jdk1.7及以上版本的特性。
 * 主类的名字必须是：Main，否则按无效代码处理。
 * <p>
 * 真实数据
 * 1-1
 * 2-1
 * 3-2
 * 4-3
 * 5-8
 * 6-20
 *
 * 网上大神的解决方案，求解不高于十万规模的数据量不是问题
 * AC代码，矩阵幂_快速幂_矩阵乘法_模板
 */
public class Main2 {

    private static int n;
    private static long mod = 1000000009;
    private static long[] f;
    private static long[] inv;

    /**
     * 记录该点的孩子节点+自身的总数
     */
    private static int[] s;
    private static long[] dp;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();

        f = new long[n + 5];
        inv = new long[n + 5];

        s = new int[n + 5];
        dp = new long[n + 5];

        f[0] = 1;
        
        for (int i = 1; i < n + 5; i++) {
            f[i] = f[i - 1] * i % mod;
            inv[i] = mpow(f[i], mod - 2);
        }

        //类似堆的找孩子
        for (int i = n; i >= 1; i--)
        {
            //C[i]<=n所以不用取余
            s[i] = 1 + (2 * i <= n ? s[2 * i] : 0) + (2 * i + 1 <= n ? s[2 * i + 1] : 0);
        }


        for (int i = 1; i < n + 5; i++) {
            dp[i] = 1;
        }

        for (int i = n; i >= 1; i--) {
            if (2 * i + 1 <= n) {
                //C(s[i]-1,s[i*2+1])和C(s[i]-1,s[i*2])都一样,组合对称
                dp[i] = dp[2 * i] * dp[2 * i + 1] % mod * C(s[i] - 1, s[i * 2 + 1]) % mod;
            }
        }

        System.out.println(dp[1]);
    }

    static long C(int n, int m) {
        return f[n] * inv[m] % mod * inv[n - m] % mod;
    }

    /**
     * 求a的n次幂
     * @param a
     * @param n
     * @return
     */
    static long mpow(long a, long n) {
        if (n == 0 || a == 1) {
            return 1;
        }
        long ans = 1;
        while (n != 0) {
            if (n % 2 == 1) {
                ans = a * ans % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }

        return ans;
    }

}