1089: [SCOI2003]严格n元树
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1250 Solved: 621
[Submit][Status][Discuss]
Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：
给出n, d，编程数出深度为d的n元树数目。
Input
仅包含两个整数n, d( 0 < n < = 32, 0 < = d < = 16)
Output
仅包含一个数，即深度为d的n元树的数目。
Sample Input
【样例输入1】
2 2
2 2
【样例输入2】
2 3
【样例输入3】
3 5
Sample Output
【样例输出1】
3
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
HINT
Source
【思路】
DP+高精度。
设f[i]表示高i的严格n元数的数目，并设S[i]表示f[i]的前缀和。一颗高i的严格n元树有一个根节点以及n个高不超过i-1的子树构成，每个子树方案为S[n-1]，则有转移式：
S[i]=(S[i-1]^n)+1
1表示只有一个根的情况。
高精度照着别人的写的，重载运算符，用起来比较方便。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int maxn = +;
const int rad = ; struct Bign { int N[maxn],len; };
void print(Bign a) {
printf("%d",a.N[a.len-]);
for(int i=a.len-;i>=;i--)
printf("%03d",a.N[i]); //补全位数
putchar('\n');
}
Bign operator *(Bign A,Bign B) {
Bign C;
int lena=A.len,lenb=B.len;
for(int i=;i<lena+lenb;i++) C.N[i]=;
for(int i=;i<lena;i++)
for(int j=;j<lenb;j++)
C.N[i+j] += A.N[i]*B.N[j];
C.len=A.len+B.len;
for(int i=;i<C.len;i++)
if(C.N[i]>=rad) {
if(i==C.len-)
C.len++ , C.N[i+]=C.N[i]/rad;
else C.N[i+]+=C.N[i]/rad;
C.N[i]%=rad;
}
while(C.len && !C.N[C.len-]) C.len--;
return C;
}
Bign operator ^(Bign A,int p) { //快速幂
Bign C;
C.len=; C.N[]=;
while(p) {
if(p&) C=C*A; A=A*A; p>>=;
}
return C;
}
Bign operator +(Bign A,int x) {
A.N[]+=x;
int now=;
while(A.N[now]>=rad) {
A.len=max(A.len,now+);
A.N[now+]+=A.N[now]/rad;
A.N[now]%=rad;
now++;
A.len=max(A.len,now);
}
return A;
}
Bign operator-(Bign A,Bign B) {
for(int i=;i<A.len;i++) {
A.N[i]-=B.N[i];
if(A.N[i]<)
A.N[i]+=rad , A.N[i+]--;
}
while(A.len && !A.N[A.len-]) A.len--;
return A;
} int n,d;
Bign S[]; int main() {
scanf("%d%d",&n,&d);
if(!d) { puts(""); return ; }
S[].len=; S[].N[]=;
for(int i=;i<=d;i++)
S[i]=(S[i-]^n)+;
print(S[d]-S[d-]);
return ;
}