题目描述
如果一棵树的所有非叶节点都恰好有n个儿子,那么我们称它为严格n元树。如果该树中最底层的节点深度为d
(根的深度为0),那么我们称它为一棵深度为d的严格n元树。例如,深度为2的严格2元树有三个,如下图:
给出n, d,编程数出深度为d的n元树数目。
输入格式
仅包含两个整数
输出格式
仅包含一个数,即深度为d的n元树的数目。
题目解析
一道小清新的计数题~~
设为深度为
的严格
元树数目。方便起见,定义
,即深度
的严格
元树数目。
现在我们考虑一棵深度为的严格
元树是怎样组成的。
首先,根节点必有恰好个儿子。每个儿子所在的子树一定是一棵深度
的严格
元树,按这个思路,转移就是
?显然我们计算了一些不合法的情况,若每棵子树深度均
,这棵树深度就无法达到
。稍微改变一下思路,考虑枚举深度恰好为
的子树,则有
这样我们就保证至少有一棵子树的深度达到,其他子树
,满足题意。
令人比较不爽的是需要用高精度计算。答案可能非常大,原题保证答案不超过200位10进制整数,然而BZOJ上似乎没写,还以为自己高精度姿势不对呢……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
/************************************************************** Problem: 1089 User: frank_c1 Language: C++ Result: Accepted Time:928 ms Memory:73204 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct ext { int num[5005],top; ext(int a=0) {*this=a;} int& operator[] (int k) {return num[k];} inline void clear() {top=0;memset(num,0,sizeof(num));} ext operator = (int x) { clear(); if(!x) num[++top]=0; else for(;x;num[++top]=x%10,x/=10); return *this; } inline void modify() { int i=1,x=0; for(;x || i<=top;i++) { x+=num[i]; num[i]=x%10;x/=10; } top=max(top,i-1); for(;top>1 && !num[top];top--); } inline void print() {PER(i,top,1) printf("%d",num[i]);} }; ext operator + (ext a,ext b) { ext c; c.top=max(a.top,b.top); REP(i,1,c.top) c[i]=a[i]+b[i]; c.modify(); return c; } ext operator * (ext a,ext b) { ext c; c.top=a.top+b.top-1; REP(i,1,a.top) REP(j,1,b.top) c[i+j-1]+=a[i]*b[j]; c.modify(); return c; } const int maxn=35; ext f[maxn][maxn],g[maxn][maxn],C[maxn][maxn]; int main() { int n,d; read(n);read(d); REP(i,0,n) C[i][0]=1; REP(i,1,n) REP(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j]; f[0][0]=g[0][0]=1; REP(i,1,n) f[0][i]=1; REP(i,1,d) { f[i][0]=g[i][0]=1; REP(j,1,n) f[i][1]=f[i][1]+C[n][j]*f[i-1][j]*g[i-1][n-j]; g[i][1]=g[i-1][1]+f[i-1][1]; REP(j,2,n) f[i][j]=f[i][j-1]*f[i][1]; REP(j,2,n) g[i][j]=g[i][j-1]*g[i][1]; } f[d][1].print();putchar('\n'); return 0; } |