¶
1)) 기 2 깊 2 리 리 모든 노드 개 = (2^(2+1) - 1)/(2-1) = 7개
2)) 1 7개 루 1개를 뺀 3개를 기 2 맞게 3개 3개 나 다.
것 combination(루를 뺀 노드 , 루를 뺀 노드 /기) 다.
combination(6, 6/2) 되고 렇게 뽑 것 두가로 므로 2! 는 방법 다.
깊 1 경 = 기! * combination(루를 뺀 노드, 루를 뺸 노드/기)
과 다 깊 2 리는 깊 1 노드를 루로 는 또 다른 나 리 리로 각 공 반복면 된다.
드 ¶
~cpp
#include <iostream>
#include <cmath>
#include "BigInteger.h"
using BigMath::BigInteger;
int depth, level, nodeNum, temp, templevel, tempdepth, select, i;
BigInteger labelingNum;
BigInteger factorial[3300];
void InitFactorial()
{
factorial[1] = 1;
for(i=2; i<3300; i++)
factorial[i] = factorial[i-1] * i;
}
BigInteger combination(int a, int b)
{
if(a==b)
return 1;
return factorial[a]/(factorial[b]*factorial[a-b]);
}
BigInteger getCompleteTreeLabeling(int l, int d)
{
labelingNum=1;
tempdepth=1;
if(l==1)
return 1;
nodeNum = (pow(l, d+1)-1)/(l-1);
nodeNum--;
while(true)
{
if(nodeNum==0)
return labelingNum/l;
select = nodeNum/l;
labelingNum = labelingNum * factorial[l] * combination(nodeNum, select);
nodeNum = select-1;
tempdepth++;
}
}
int main()
{
InitFactorial();
while(cin>>level>>depth)
cout << getCompleteTreeLabeling(level, depth) << endl;
return 0;
}
