首页 > 代码库 > BZOJ1089: [SCOI2003]严格n元树
BZOJ1089: [SCOI2003]严格n元树
1089: [SCOI2003]严格n元树
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 762 Solved: 387
[Submit][Status]
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 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位，看起来貌似不可能那么少。。。
高精度乘高精度太浪费时间了，我暂时没有想到好的解决办法。
贴一下上面的代码（没有用累加法）
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 namespace std; 46 47 inline int read() 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,int x) 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 int main()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 }
BZOJ1089: [SCOI2003]严格n元树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。