UVa 10247 Complete Tree Labeling:组合数学&高精度

10247 - Complete Tree Labeling

Time limit: 15.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1188

A complete k-ary tree is a k-ary tree in which all leaves have same depth and all internal nodes have degree k. This k is also known as the branching factor of a tree. It is very easy to determine the number of nodes of such a tree. Given the depth and branching factor of such a tree, you will have to determine in how many different ways you can number the nodes of the tree so that the label of each node is less that that of its descendants. You should assume that for numbering a tree with N nodes you have the (1, 2, 3, N-1, N) labels available.

Input

The input file will contain several lines of input. Each line will contain two integers k and d. Here k is the branching factor of the complete k-arytree and d is the depth of the complete k-ary tree (k>0, d>0, k*d<=21).

Output

For each line of input, produce one line of output containing a round number, which is the number of ways the k-ary tree can be labeled, maintaining the constraints described above.

Sample Input:

2 2

10 1

Sample Output:

80

3628800

思路:

用ans[i][j]表示深度为j的满i叉树的标号方案数,用node[i][j]表示深度为j的满i叉树的结点数。首先根结点必定是标最小的号码,然后还剩下node[i][j]-1个号码可用,我们要将他们分配给i棵子树,每棵子树得到m=node[i][j-1]个号码。用c[n][k]表示组合数,所以共有c[n[i][j]-1][m]*c[n[i][j]-1-m][m]*c[n[i][j]-1-2*m][m]*…*c[m][m]种分配方案。继续对子树标号,共有ans[i][j-1]^i种情况。故得到递归式:

本文URL地址:http://www.bianceng.cn/Programming/sjjg/201410/45357.htm

ans[i][j]=c[n[i][j]-1][m]*c[n[i][j]-1-m][m]*c[n[i][j]-1-2*m][m]*…*c[m][m]*(ans[i][j-1]^i)。

高精度注意:当k=5,d=4时,结果有1774位。

完整代码:

/*0.549s*/

import java.util.*;
import java.io.*;
import java.math.*;  

public class Main {
    static Scanner cin = new Scanner(new BufferedInputStream(System.in));
    static final int N = 22;  

    static int[][] node = new int[N][N];
    static BigInteger[][] ans = new BigInteger[N][N];  

    static BigInteger c(int n, int k) {// 计算组合数
        if (k > n)
            return BigInteger.ZERO;
        if (k > n - k)
            return c(n, n - k);
        BigInteger ans = BigInteger.ONE;
        for (int i = 0; i < k; ++i)
            ans = ans.multiply(BigInteger.valueOf(n - i)).divide(BigInteger.valueOf(i + 1));
        return ans;
    }  

    static void init() {
        for (int i = 1; i < N; ++i) {
            int pow = 1;
            node[i][0] = 1;
            for (int j = 1; j < N; ++j) {
                pow *= i;
                node[i][j] = node[i][j - 1] + pow;// 计算深度为j的满i叉树的结点数
            }
        }
        for (int i = 1; i < N; ++i) {
            ans[i][0] = BigInteger.ONE;
            for (int j = 1; i * j < N; ++j) {
                ans[i][j] = BigInteger.ONE;
                int m = node[i][j - 1];
                for (int k = 0; k < i; ++k)
                    ans[i][j] = ans[i][j].multiply(ans[i][j - 1]).multiply(c(node[i][j] - 1 - k * m, m));// 计算结果
            }
        }
    }  

    public static void main(String[] arg) {
        init();
        while (cin.hasNextInt())
            System.out.println(ans[cin.nextInt()][cin.nextInt()]);
    }
}

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, for
, node
, tree
, biginteger
The
complete binary tree、complete tree、10247、乐高10247、lego 10247,以便于您获取更多的相关知识。

时间: 2024-10-26 06:32:14

UVa 10247 Complete Tree Labeling:组合数学&amp;高精度的相关文章

UVa 10198 Counting:组合数学&amp;amp;高精度

10198 - Counting Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1139 The Problem Gustavo knows how to count, but he is now learning how write numbers. As

UVa 10157 Expressions:组合数学&amp;amp;高精度

10157 - Expressions Time limit: 10.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1098 Let X be the set of correctly built parenthesis expressions. The elements of X a

UVa 748/POJ 1001 Exponentiation:浮点高精度求幂&amp;amp;正则表达式的应用

748 - Exponentiation Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=97&page=show_problem&problem=689 http://poj.org/problem?id=1001 Problems involving the computation of exact values

UVa 112:Tree Summing 二叉树构造, 二叉树路径和

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=48&mosmsg=Submission+received+with+ID+10280379 题目类型: 数据结构, 二叉树 加强版样例输入: 22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))

UVa 548:Tree 二叉树的重建——中序遍历与后续遍历进行建树

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489 题目类型: 数据结构, 二叉树 题目大意: 给两个组数字,都是在同一棵二叉树上的,第一组是按中序遍历(inorder)顺序输出的,第二组是按后序遍历(postorder)输出的, 根据这两组数据构建出原来的二叉树,然后计算从根结点到每个叶子结

UVa 10013 Super long sums:简单高精度

10013 - Super long sums Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=954 The Problem The creators of a new programming language D++ have found out that

UVa 10220 I Love Big Numbers ! (简单高精度)

10220 - I Love Big Numbers ! Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1161 The Problem A Japanese young girl went to a Science Fair at Tokyo. There

LeetCode All in One 题目讲解汇总(持续更新中...)

终于将LeetCode的免费题刷完了,真是漫长的第一遍啊,估计很多题都忘的差不多了,这次开个题目汇总贴,并附上每道题目的解题连接,方便之后查阅吧~ 如果各位看官们,大神们发现了任何错误,或是代码无法通过OJ,或是有更好的解法,或是有任何疑问,意见和建议的话,请一定要在对应的帖子下面评论区留言告知博主啊,多谢多谢,祝大家刷得愉快,刷得精彩,刷出美好未来- 博主制作了一款iOS的应用"Leetcode Meet Me",里面有Leetcode上所有的题目,并且贴上了博主的解法,随时随地都能

UVa 10254 The Priest Mathematician:组合数学&amp;amp;规律发现&amp;amp;高精度

10254 - The Priest Mathematician Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1195 The ancient folklore behind the "Towers of Hanoi" puzzle i