首页 > 代码库 > SCOI2003 BZOJ1089 严格N元树
SCOI2003 BZOJ1089 严格N元树
个人认为这是一道比较诡异的题，首先分享题目
如下：
描述
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：
给出n, d，编程数出深度为d的n元树数目。( 0 < n < = 32, 0 < = d < = 16)
样例如下：
【样例输入 1 】
2 2
【样例输出 1 】
3
【样例输入 2 】
2 3
【样例输出 2 】
21
【样例输入 3 】
3 5
2 2
【样例输出 1 】
3
【样例输入 2 】
2 3
【样例输出 2 】
21
【样例输入 3 】
3 5
【样例输出 3 】
58871587162270592645034001
58871587162270592645034001
看到样例3的输出我就笑了
这道题也在openjudge上出过，说保证输出不超过200位的整数→_→。
我谢谢你。
好的接下来讲一下这道题的思路：
我们设定最大高度为i的子树个数有
首先，明显的，深度为0的的子树个数为1；及f[0]=1.
其次，对于剩下的f[i]来说，f[i]=f[i-1]^n+1；及因为有n个分支，所以要先取一个f[i-1]^n，然后加上一个什么都不加的情况，所以可得到递推式。
然后循环到b的时候我们实际上输出的是f[i]-f[i-1]为什么捏，原因很简单，因为我们算的f[i]实际上是高度为 i 的子树的前缀和，所以我们要剪掉高度为i-1的不符合题意的情况，
贴出超来的代码→_→
1 #include<cstdio> 2 2 #include<cstring> 3 3 #include<iostream> 4 4 using namespace std; 5 5 6 6 const int maxn = 5000+10; 7 7 const int rad = 1000; 8 8 9 9 struct Bign { int N[maxn],len; };10 10 void print(Bign a) {11 11 printf("%d",a.N[a.len-1]);12 12 for(int i=a.len-2;i>=0;i--)13 13 printf("%03d",a.N[i]); //补全位数 14 14 putchar(‘\n‘);15 15 }16 16 Bign operator *(Bign A,Bign B) {17 17 Bign C;18 18 int lena=A.len,lenb=B.len;19 19 for(int i=0;i<lena+lenb;i++) C.N[i]=0;20 20 for(int i=0;i<lena;i++)21 21 for(int j=0;j<lenb;j++)22 22 C.N[i+j] += A.N[i]*B.N[j];23 23 C.len=A.len+B.len;24 24 for(int i=0;i<C.len;i++) 25 25 if(C.N[i]>=rad) {26 26 if(i==C.len-1) 27 27 C.len++ , C.N[i+1]=C.N[i]/rad;28 28 else C.N[i+1]+=C.N[i]/rad;29 29 C.N[i]%=rad;30 30 }31 31 while(C.len && !C.N[C.len-1]) C.len--;32 32 return C;33 33 }34 34 Bign operator ^(Bign A,int p) { //快速幂 35 35 Bign C;36 36 C.len=1; C.N[0]=1;37 37 while(p) {38 38 if(p&1) C=C*A; A=A*A; p>>=1;39 39 }40 40 return C;41 41 }42 42 Bign operator +(Bign A,int x) {43 43 A.N[0]+=x;44 44 int now=0;45 45 while(A.N[now]>=rad) {46 46 A.len=max(A.len,now+1);47 47 A.N[now+1]+=A.N[now]/rad;48 48 A.N[now]%=rad;49 49 now++;50 50 A.len=max(A.len,now);51 51 }52 52 return A;53 53 }54 54 Bign operator-(Bign A,Bign B) {55 55 for(int i=0;i<A.len;i++) {56 56 A.N[i]-=B.N[i];57 57 if(A.N[i]<0)58 58 A.N[i]+=rad , A.N[i+1]--;59 59 }60 60 while(A.len && !A.N[A.len-1]) A.len--;61 61 return A;62 62 }63 63 64 64 int n,d;65 65 Bign S[50];66 66 67 67 int main() {68 68 scanf("%d%d",&n,&d);69 69 if(!d) { puts("1"); return 0; }70 70 S[0].len=1; S[0].N[0]=1;71 71 for(int i=1;i<=d;i++)72 72 S[i]=(S[i-1]^n)+1;73 73 print(S[d]-S[d-1]);74 74 return 0;75 75 }
百度第一页都一个代码，及以上这段代码，然后不只一篇博客上有作者版权之类的话。。。
SCOI2003 BZOJ1089 严格N元树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。