摘要：
如果该树中最底层的节点深度为d，那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：给出n,d，编程数出深度为d的n元树数目。Input仅包含两个整数n,dOutput仅包含一个数，即深度为d的n元树的数目。）考虑递推解此题：设f[i]表示深度为i的严格n元树的数目，g[i]表示深度为的严格n元树的数目。则我们有如下递推式：1.f[i]=g[i-1]^n-g[i-2]^n2.g[i]=g[i-1]+f[i]第二个是显然的，我们来说一下第一个是怎么来的。贴一下上面的代码1#include23#include45#include67#include89#include1011#include1213#include1415#include1617#include1819#include2021#include2223#defineinf10000000002425#definemaxn502627#definemaxm5000002829#defineeps1e-103031#definelllonglong3233#definepapair3435#definefor0(i,n)for3637#definefor1(i,n)for3839#definefor2for4041#definefor3for4243#definemod100004445usingnamespacestd;4647inlineintread()4849{5051intx=0,f=1;charch=getchar();5253while{iff=-1;ch=getchar();}5455while{x=10*x+ch-'0';ch=getchar();}5657returnx*f;5859}60intn,m,f[maxn][maxm],g[2][maxm],t[maxm],c[maxm];61inlinevoidwriteln62{63cout˂˂a[a[0]];64for3cout˂˂a[i];cout˂˂endl;65}66inlinevoidupdate67{68for169{70a[i+1]+=a[i]/mod;71a[i]%=mod;72ifa[0]++;73}74}75inlinevoidmul76{77for1a[i]*=x;78update;79}80inlinevoidjia81{82a[0]=max;83for184{85a[i]+=b[i];86a[i+1]+=a[i]/mod;87a[i]%=mod;88}89while(!
1089: [SCOI2003]严格n元树
Time Limit: 1 SecMemory Limit: 162 MBSubmit: 762Solved: 387
[Submit][Status]
Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：
![BZOJ1089: [SCOI2003]严格n元树第1张](http://www.lydsy.com/JudgeOnline/images/1089/1.jpg)
给出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
2 2
【样例输入2】
2 3
【样例输入3】
3 5
Sample Output
【样例输出1】
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
HINT
Source
题解：
先说一下此题我的想法（尽管没有A掉。。。）
考虑递推解此题：
设f[i]表示深度为i的严格n元树的数目，g[i]表示深度为（1--i）的严格n元树的数目。
则我们有如下递推式：
1.f[i]=g[i-1]^n-g[i-2]^n
2.g[i]=g[i-1]+f[i]
第二个是显然的，我们来说一下第一个是怎么来的。
因为我们从i-1递推到i，所以考率在n棵子树上加一个根节点，其余为原先的子树
因为要保证这棵树的深度达到n，所以至少有一个子树的深度达到n-1，
所以每个子树可以有g[i-1]种形态，n棵就是g[i-1]^n，然后去掉不合法的，
不合法的就是每个子树的深度都在1--i-2，即有g[i-2]种选择，也就是 g[i-2]^n
然后如果我们使用累加法的话可以发现 g[i]=g[i-1]^n+1，貌似很简单了？
TLE！！！尽管没有试，但我想是这样的，因为这个复杂度的话，ans必须<=4000位，看起来貌似不可能那么少。。。
高精度乘高精度太浪费时间了，我暂时没有想到好的解决办法。
贴一下上面的代码（没有用累加法）
![BZOJ1089: [SCOI2003]严格n元树第2张](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![BZOJ1089: [SCOI2003]严格n元树第3张](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 50 26 27 #define maxm 500000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 10000 44 45 using namespacestd; 46 47 inline intread() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 54 55 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,f[maxn][maxm],g[2][maxm],t[maxm],c[maxm]; 61 inline void writeln(int *a) 62 { 63 cout<<a[a[0]]; 64 for3(i,a[0]-1,1)cout<<a[i];cout<<endl; 65 } 66 inline void update(int *a) 67 { 68 for1(i,a[0]) 69 { 70 a[i+1]+=a[i]/mod; 71 a[i]%=mod; 72 if(a[a[0]+1])a[0]++; 73 } 74 } 75 inline void mul(int *a,intx) 76 { 77 for1(i,a[0])a[i]*=x; 78 update(a); 79 } 80 inline void jia(int *a,int *b) 81 { 82 a[0]=max(a[0],b[0]); 83 for1(i,a[0]) 84 { 85 a[i]+=b[i]; 86 a[i+1]+=a[i]/mod; 87 a[i]%=mod; 88 } 89 while(!a[a[0]])a[0]--; 90 } 91 inline void cheng(int *a,int *b) 92 { 93 memset(c,0,sizeof(c)); 94 for1(i,a[0]) 95 for1(j,b[0]) 96 { 97 c[i+j-1]+=a[i]*b[j]; 98 c[i+j]+=c[i+j-1]/mod; 99 c[i+j-1]%=mod; 100 } 101 c[0]=a[0]+b[0]+1; 102 while(!c[c[0]]&&c[0])c[0]--; 103 memcpy(a,c,sizeof(c)); 104 } 105 inline void jian(int *a,int *b) 106 { 107 for1(i,a[0]) 108 { 109 a[i]-=b[i]; 110 if(a[i]<0)a[i]+=mod,a[i+1]-=1; 111 } 112 while(!a[a[0]])a[0]--; 113 } 114 115 intmain() 116 117 { 118 119 freopen("input.txt","r",stdin); 120 121 freopen("output.txt","w",stdout); 122 123 n=read();m=read(); 124 f[1][f[1][0]=1]=1; 125 g[0][g[0][0]=1]=1; 126 g[1][g[1][0]=1]=2; 127 for2(i,2,m) 128 { 129 f[i][f[i][0]=1]=1; 130 for1(j,n)cheng(f[i],g[1]); 131 t[t[0]=1]=1; 132 for1(j,n)cheng(t,g[0]); 133 jian(f[i],t); 134 jia(g[0],f[i-1]); 135 jia(g[1],f[i]); 136 } 137 printf("%d",f[m][f[m][0]]); 138 for3(i,f[m][0]-1,1)printf("%04d",f[m][i]); 139 140 return 0; 141 142 }
感觉不会再爱了，这居然就是正解QAQ
不会貌似别人解释的更简单，直接推g[i]的表达式也很简单。
妈蛋，数据范围给的太大了，和lydsy要过来数据发现全是非常小的T_T
我做了2天多，一直在对拍自己的程序为什么出错，AC的程序运行过程中答案为什么会越来越小，我的程序为什么10 15的点都跑不出来，而且位数剧增
今天才发现是别人的空间爆了啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
还以为是我的程序错了啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
看来我的推断没有错，如果数据范围真如题中所说，那么答案的位数就太大了。
我要去建议lydsy修改此题的题面，不要再像坑我一样坑了其他人。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 500+100 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 10000 23 using namespacestd; 24 inline intread() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 28 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} 29 return x*f; 30 } 31 classbigg 32 { 33 public: 34 intnum[maxn], len; 35 bigg() 36 { 37 memset(num,0,sizeof(num)); 38 len=0; 39 } 40 bigg operator = (const bigg &b) 41 { 42 memset(num,0,sizeof(num)); 43 len=b.len; 44 for1(i,len)num[i]=b.num[i]; 45 return(*this); 46 } 47 bigg operator = (intb) 48 { 49 memset(num,0,sizeof(0)); 50 if (b==0) 51 { 52 len=1; 53 return(*this); 54 } 55 len=0; 56 while(b>0) 57 { 58 num[++len]=b%mod; 59 b/=mod; 60 } 61 return (*this); 62 } 63 bigg operator * (const bigg &b) 64 { 65 bigg ans; 66 ans=0; 67 if (len==1&&num[1]==0||b.len==1&&b.num[1]==0) 68 returnans; 69 ans.len=len+b.len-1; 70 for1(i,len) 71 for1(j,b.len) 72 { 73 ans.num[i+j-1]+=num[i]*b.num[j]; 74 ans.num[i+j]+=ans.num[i+j-1]/mod; 75 ans.num[i+j-1]%=mod; 76 } 77 if (ans.num[ans.len+1])ans.len++; 78 while(!ans.num[ans.len])ans.len--; 79 returnans; 80 } 81 bigg operator - (const bigg &b) 82 { 83 bigg ans; 84 ans=0; 85 ans.len=len; 86 for1(i,len) 87 { 88 ans.num[i]+=num[i]-b.num[i]; 89 if (ans.num[i]<0) 90 { 91 ans.num[i+1]--; 92 ans.num[i]+=mod; 93 } 94 } 95 while (ans.len>1&&!ans.num[ans.len]) ans.len--; 96 returnans; 97 } 98 bigg operator + (const bigg &b) 99 { 100 bigg ans; 101 ans=0; 102 ans.len=max(len,b.len); 103 for1(i,ans.len) 104 { 105 ans.num[i]+=num[i]+b.num[i]; 106 ans.num[i+1]=ans.num[i]/mod; 107 ans.num[i]%=mod; 108 } 109 if (ans.num[ans.len+1])ans.len++; 110 returnans; 111 } 112 voidprint() 113 { 114 printf("%d",num[len]); 115 for3(i,len-1,1)printf("%04d",num[i]); 116 printf(""); 117 } 118 }; 119 120 intmain() 121 { 122 freopen("input.txt","r",stdin); 123 freopen("output.txt","w",stdout); 124 intn, deep; 125 scanf("%d%d", &n, &deep); 126 if (deep == 0) 127 { 128 printf("1 "); 129 return 0; 130 } 131 bigg fpre, fnow, f1; 132 fpre=1,f1=1; 133 for1(i,deep) 134 { 135 fnow=1; 136 for1(j,n)fnow=fnow*fpre; 137 fnow=fnow+f1; 138 if (i!= deep) fpre=fnow; 139 } 140 fnow=fnow-fpre; 141 fnow.print(); 142 return 0; 143 } 144
不过还是有几点收获的：
1.捞到一个高精度模版
2.class里数组要开小