Description
如果一棵树的所有非叶节点都恰好有n个儿子,那么我们称它为严格n元树。如果该树中最底层的节点深度为d
(根的深度为0),那么我们称它为一棵深度为d的严格n元树。例如,深度为2的严格2元树有三个,如下图:
给出n, d,编程数出深度为d的n元树数目。
Input
仅包含两个整数n, d( 0 < n < = 32, 0 < = d < = 16)
Output
仅包含一个数,即深度为d的n元树的数目。
Sample Input
【样例输入1】
2 2
【样例输入2】
2 3
【样例输入3】
3 5
Sample Output
【样例输出1】
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
本想打表找规律但是d=3就数不清了
好不容易看懂题解,一个递推关系,n固定,以s[i]表示最大深度为i的严格n元树的方案数,然后从s[i-1]递推到s[i],就是就是在深度为i-1的树上再加一个根节点,然后这个根节点有n个子节点,每个点都可以连上s[i-1]那些方案的树,那这样就是s[i-1]^n,再加上1就是根不连任何子树的情况
然后最后答案就是s[d]-s[d-1]了,很强
java大数能过
代码:
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
int n,d;
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
d=cin.nextInt();
BigInteger[] s=new BigInteger[50];
if(d==0){
System.out.println(1);
}else{
s[0]=BigInteger.valueOf(1);
for(int i=1;i<=d;i++){
s[i]=(s[i-1].pow(n)).add(BigInteger.valueOf(1));
}
System.out.println(s[d].subtract(s[d-1]));
}
}
}