# 14011: 【原4011】k树

### 题目描述

author: yura 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4011

## Description

1. 根节点至多可以长出k个子节点

2. 每个节点的第i个子节点(i=0,1,2...k-1)上至多可以长出k-i个子节点

## Input Format

50%数据: $$2 \leq k \leq 10 , 2 \leq h \leq 10$$

80%数据: $$2 \leq k \leq 20 , 2 \leq h \leq 20$$

100%数据: $$2 \leq k \leq 50 , 2 \leq h \leq 50$$

## Sample Input

3 3


## Sample Output

6


## ligongzzz's solution

#include "iostream"
#include "cstring"
#include "cmath"
#include "algorithm"

using namespace std;

//常数
constexpr auto maxNum = 10000;
constexpr auto intMax = 20;

//新无符号大整数类
class unsignedBigInt {
private:
bool del = false;
public:
char* ch;
int startNum = 0;
int len = 0;

//初始化
unsignedBigInt(const char* input) {
if (del)
delete[] ch;

len = (strlen(input) + 1) * 2;
startNum = strlen(input);
ch = new char[len];
memset(ch, 0, len);
for (int i = 0; i < strlen(input); i++)
ch[i + startNum] = input[i];

del = true;
}
unsignedBigInt(int num) {
if (del)
delete[] ch;

//临时数组
int n = 0, temp[intMax];
if (num == 0) {
n = 1;
temp[0] = 0;
}
else
for (; num > 0; num /= 10)
temp[n++] = num % 10;

len = (n + 1) * 2;
startNum = n;
ch = new char[len];
memset(ch, 0, len);

for (int i = 0; i < n; i++)
ch[startNum + i] = temp[n - i - 1] + '0';

del = true;
}
unsignedBigInt(void) {
if (del)
delete[] ch;

len = 1;
startNum = 0;
ch = new char[len];
memset(ch, 0, len);

del = true;
}
unsignedBigInt(int num, int sizen) {
if (del)
delete[] ch;

len = (sizen + 1) * 2;
startNum = sizen;
ch = new char[len];
memset(ch, 0, len);

if (num >= 0) {
int n = 0, temp[intMax];
if (num == 0) {
n = 1;
temp[0] = 0;
}
else
for (; num > 0; num /= 10)
temp[n++] = num % 10;

for (int i = 0; i < n; i++)
ch[startNum + i] = temp[n - i - 1] + '0';
}

del = true;
}

//析构
~unsignedBigInt() {
if (del)
delete[] ch;
}

//计算真实长度
int realLength(const unsignedBigInt & b) {
return strlen(b.ch + b.startNum);
}

//复制构造函数
unsignedBigInt(const unsignedBigInt & b) {
if (del)
delete[] ch;

len = b.len;
startNum = b.startNum;
ch = new char[len];
for (int i = 0; i < len; i++)
ch[i] = b.ch[i];

del = true;
}

//输入输出
friend ostream & operator<<(ostream & output, const unsignedBigInt & bi);
friend istream & operator>>(istream & input, unsignedBigInt & bi);

//赋值
unsignedBigInt & operator=(const unsignedBigInt & b) {
//检查自身赋值
if (this == &b)
return *this;

if (del)
delete[] ch;

len = b.len;
startNum = b.startNum;
ch = new char[len];
for (int i = 0; i < len; i++)
ch[i] = b.ch[i];

del = true;
return *this;
}

unsignedBigInt & operator=(int num) {
if (del)
delete[] ch;

//临时数组
int n = 0, temp[intMax];
if (num == 0) {
n = 1;
temp[0] = 0;
}
else
for (; num > 0; num /= 10)
temp[n++] = num % 10;

len = (n + 1) * 2;
startNum = n;
ch = new char[len];
memset(ch, 0, len);

for (int i = 0; i < n; i++)
ch[startNum + i] = temp[n - i - 1] + '0';

del = true;
return *this;
}

//比较符
//大于
bool operator>(const unsignedBigInt & b) {
return (strcmp(ch + startNum, b.ch + b.startNum) > 0 && strlen(ch + startNum) == strlen(b.ch + b.startNum)) || strlen(ch + startNum) > strlen(b.ch + b.startNum) ? true : false;
}
//运算符
//加号
unsignedBigInt operator+(const unsignedBigInt & b) {
unsignedBigInt temp(-1, max(realLength(*this), realLength(b)) + 2);
int jw = 0;
int test = realLength(*this);

for (int i = 0; realLength(*this) > i || realLength(b) > i || jw != 0; i++) {
//判断加数
int j1 = realLength(*this) <= i ? 0 : ch[startNum + strlen(ch + startNum) - i - 1] - '0';
int j2 = realLength(b) <= i ? 0 : b.ch[b.startNum + strlen(b.ch + b.startNum) - i - 1] - '0';

//运算
temp.ch[--temp.startNum] = (j1 + j2 + jw) % 10 + '0';
jw = (j1 + j2 + jw) / 10;
}

//返回
return temp;
}
};

//输入输出流重载
//无符号大整数
ostream& operator<<(ostream & output, const unsignedBigInt & bi) {
output << bi.ch + bi.startNum;
return output;
}
istream& operator>>(istream & input, unsignedBigInt & bi) {
char ch[maxNum];
input >> ch;
bi = unsignedBigInt(ch);
return input;
}

unsignedBigInt numData[51][51];
int k, h;
void cnt(int num, int depth) {
if (depth == 1) {
numData[num][depth] = 1;
return;
}
if (numData[num][depth] > 0)
return;
//遍历
for (int i = 0; i < num; i++) {
cnt(k - i, depth - 1);
numData[num][depth] = numData[num][depth] + numData[k - i][depth - 1];
}
return;
}

int main() {
cin >> k >> h;
for (int i = 0; i <= k; i++)
for (int j = 0; j <= h; j++)
numData[i][j] = 0;
cnt(k, h);

cout << numData[k][h];

return 0;
}


## Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 10000;

class bigint {
private:
long long data[20];
const long long base = 1e8;

public:
bigint(int x = 0);
bigint& operator=(const bigint&);
bigint operator+(const bigint&) const;
bool operator==(const int) const;
void output() const;
};

bigint::bigint(int x) {
for (int i = 0; i < 20; i++) {
data[i] = 0;
}
data[0] = x;
}

bigint& bigint::operator=(const bigint& right) {
for (int i = 0; i < 20; i++) {
data[i] = right.data[i];
}

return *this;
}

bigint bigint::operator+(const bigint& right) const {
bigint ans(0);
long long carry = 0;

for (int i = 0; i < 20 && (carry || data[i] || right.data[i]); i++) {
ans.data[i] = data[i] + right.data[i] + carry;
carry = ans.data[i] / base;
ans.data[i] %= base;
}

return ans;
}

bool bigint::operator==(const int x) const {
for (int i = 19; i > 0; i--) {
if (data[i] != 0) {
return 0;
}
}

return data[0] == x;
}

void bigint::output() const {
int i = 19;
while (data[i] == 0) {
i--;
}

printf("%lld", data[i]);
i--;
for (; i >= 0; i--) {
printf("%08lld", data[i]);
}

return;
}

bigint dp[maxN][maxN];

bigint DP(int, int, int);

int main() {
int k, h;
bigint ans;

scanf("%d%d", &k, &h);
ans = DP(k, h, k);

ans.output();

return 0;
}

bigint DP(int a, int b, int k) {
if (!(dp[a][b] == 0)) {
return dp[a][b];
} else if (b == 2) {
dp[a][b] = a;
return dp[a][b];
} else {
for (int i = 0; i < a; i++) {
dp[a][b] = dp[a][b] + DP(k - i, b - 1, k);
}
return dp[a][b];
}
}


## q4x3's solution

/**
* 一道简单的dp
* 难就难在大整数。。。
**/
#include <iostream>
#include <cstring>

using namespace std;

class bigint {
public:
char dt[100];

bigint():dt("0") {}
bigint &operator=(const bigint &obj) {
strcpy(dt, obj.dt);
return *this;
}
bigint &operator=(const int &obj) {
dt[0] = obj + '0';
dt[1] = 0;
return *this;
}
friend ostream& operator<<(ostream &os, const bigint &obj);
friend bigint operator+(const bigint &i1, const bigint &i2);
};

ostream& operator<<(ostream &os, const bigint &obj) {
for(int i = strlen(obj.dt) - 1;i >= 0;-- i) cout << obj.dt[i];
}

bigint operator+(const bigint &i1, const bigint &i2) {
int carry = 0;
int len = max(strlen(i1.dt), strlen(i2.dt));
bigint tmp;
for(int i = 0;i < len;++ i) {
int tmp1, tmp2;
if(i >= strlen(i1.dt)) tmp1 = 0;
else tmp1 = i1.dt[i] - '0';
if(i >= strlen(i2.dt)) tmp2 = 0;
else tmp2 = i2.dt[i] - '0';
int sum = tmp1 + tmp2 + carry;
tmp.dt[i] = sum % 10 + '0';
carry = sum / 10;
}
if(carry) {
tmp.dt[len] = '1';
tmp.dt[len + 1] = 0;
} else {
tmp.dt[len] = 0;
}
return tmp;
}

bigint a[60][60];
int k, h;

int main() {
scanf("%d%d", &k, &h);
for(int j = 1;j <= k;++ j) a[1][j] = 1;
for(int i = 2;i <= h;++ i) {
for(int j = 1;j <= k;++ j) {
a[i][j] = a[i][j - 1] + a[i - 1][k - j + 1];
}
}
cout << a[h][k] << endl;
return 0;
}


## victrid's solution

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
class ulll {
private:
unsigned long long data[20];
int getDigitNum(unsigned long long n) const {
int dig = 1;
if (n >= 10000000000000000ull) {
n /= 10000000000000000ull;
dig += 16;
}
if (n >= 100000000ull) {
n /= 100000000ull;
dig += 8;
}
if (n >= 10000ull) {
n /= 10000ull;
dig += 4;
}
if (n >= 100ull) {
n /= 100ull;
dig += 2;
}
while (n >= 10ull) {
n /= 10ull;
dig += 1;
}
return dig;
}

public:
operator bool() const {
for (int i = 19; i >= 0; i--) {
if (data[i] != 0)
return true;
}
return false;
}
ulll() {
for (int i = 0; i < 20; i++) {
data[i] = 0;
}
}
ulll(long long init) {
for (int i = 1; i < 20; i++) {
data[i] = 0;
}
data[0] = abs(init);
return;
}
ulll& operator+=(const ulll& rhs) {
for (int i = 0; i < 20; i++) {
data[i] += rhs.data[i];
while (i != 19 && data[i] >= 10000000000000000000ull) {
data[i + 1] += 1;
data[i] -= 10000000000000000000ull;
};
}
return *this;
}
void print() const {
bool nof = 0;
if (!*this) {
putchar('0');
return;
}
for (int i = 19; i >= 0; i--) {
if (!nof && data[i] == 0)
continue;
if (nof) {
int p = 19 - getDigitNum(data[i]);
while (p--)
putchar('0');
}
nof = 1;
printf("%llu", data[i]);
}
return;
}
};

ulll k_h[55][55];

ulll DP(int d, int h, int k) {
if (k_h[d][h])
return k_h[d][h];
if (h == 2) {
k_h[d][h] = d;
return k_h[d][h];
}
for (int i = 0; i < d; i++) {
k_h[d][h] += DP(k - i, h - 1, k);
}
return k_h[d][h];
}
int main() {
int k, h;
scanf("%d%d", &k, &h);
for (int i = 0; i < 55; i++) {
for (int j = 0; j < 55; j++) {
k_h[i][i] = 0;
}
}
DP(k, h, k).print();
return 0;
}


## WashSwang's solution

#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;
const int p=1000000000;
//Same as 4152
class longint{

long long num[3000];
int len;
public:
longint(){
memset(num,0,sizeof(num));
len=1;
};

longint(const char *s){
memset(num,0,sizeof(num));
int l=(strlen(s)-1)/9+1,length=strlen(s);
for (int i=0;i<l;++i){
for (int j=length-9*i-9;j<length-9*i;++j)
if (j>=0)
num[i]=num[i]*10+s[j]-48;
}
len=l;
}

longint(int x){
memset(num,0,sizeof(num));
len=0;
while (x!=0)
{
num[len++]=x%p;
x/=p;
}
}

longint(const longint &a):len(a.len){
memset(num,0,sizeof(num));
for (int i=0;i<a.len;++i)
num[i]=a.num[i];
}

longint &operator=(const longint& a){
memset(num,0,sizeof(num));
len=a.len;
for (int i=0;i<a.len;++i)
num[i]=a.num[i];
return *this;
}

friend longint operator+(const longint& a,const longint& b){
long long c=0;
longint r;
r.len=max(a.len,b.len);
for (int i=0;i<r.len;++i){
r.num[i]=a.num[i]+b.num[i]+c;
c=r.num[i]/p;
r.num[i]%=p;
}
if (c>0) r.num[r.len++]=c;
return r;
}

friend longint operator-(const longint& a,const longint& b){
int c=0;
longint r;
r.len=max(a.len,b.len);
for (int i=0;i<max(a.len,b.len);++i){
r.num[i]=a.num[i]-b.num[i]-c;
c=0;
if (r.num[i]<0){
r.num[i]+=p;
c=1;
}
}
while (r.len>1&&!r.num[r.len-1]) r.len--;
return r;
}

friend longint operator*(const longint& a,const longint& b){
long long c=0,pos;
int x=0;
longint r;
for (int i=0;i<b.len;++i){
x=i;
c=0;
longint tmp;
for (int j=0;j<a.len;++j){
pos=a.num[j]*b.num[i]+c;
c=pos/p;
tmp.num[x]=pos%p;
x++;
}
tmp.len=x;
if (c>0) tmp.num[tmp.len++]=c;
r=r+tmp;
}
return r;
}

friend longint div(const longint& a){
longint r;
long long x=0;
for (int i=a.len-1;i>=0;i--){
x=x*p+a.num[i];
r.num[i]=x/2;
x%=2;
}
r.len=a.len;
if (!r.num[r.len-1]) r.len--;
return r;
}

friend bool operator>(const longint& a,const longint& b){
if (a.len>b.len) return true;
if (a.len<b.len) return false;
for (int i=a.len-1;i>=0;--i){
if (a.num[i]>b.num[i]) return true;
if (a.num[i]<b.num[i]) return false;
}
return false;
}

friend ostream& operator<<(ostream& os,const longint &a){
os.fill('0');
os<<a.num[a.len-1];
for (int i=a.len-2;i>=0;--i) {
os<<setw(9)<<a.num[i];
}
return os;
}

friend bool odd(longint &a){
return a.num[0]%2!=0;
}
};
longint x[51][51];
int h,k;
int main() {
cin>>k>>h;
for (int i=0;i<=k-1;++i) x[1][i]=k-i;
for (int i=2;i<=h-1;++i){
for (int j=0;j<=k-1;++j)
for (int l=0;l<k-j;++l) x[i][j]=x[i][j]+x[i-1][l];
}
cout<<x[h-1][0];
}