Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:05Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 23:		Line 23:
	BigInteger labelingNum;		BigInteger labelingNum;

	BigInteger factorial[3300];		BigInteger factorial[3300];

	void InitFactorial()		void InitFactorial()
	{		{
	factorial[1] = 1;		factorial[1] = 1;
	for(i=2; i<3300; i++)		for(i=2; i<3300; i++)
	factorial[i] = factorial[i-1] * i;		factorial[i] = factorial[i-1] * i;
	}		}

Line 36:		Line 36:
	if(a==b)		if(a==b)
	return 1;		return 1;
	return factorial[a]/(factorial[b]*factorial[a-b]);		return factorial[a]/(factorial[b]*factorial[a-b]);
	}		}

Line 52:		Line 52:
	return labelingNum/l;		return labelingNum/l;
	select = nodeNum/l;		select = nodeNum/l;
	labelingNum = labelingNum * factorial[l] * combination(nodeNum, select);		labelingNum = labelingNum * factorial[l] * combination(nodeNum, select);
	nodeNum = select-1;		nodeNum = select-1;
	tempdepth++;		tempdepth++;

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:58Z

New page

== 풀이 ==

모든 경우에 답이 다 나오나 결과는 런타임 에러~~(찾을 수 있는 사람 있으면 찾아봐줘~~)

일단 컴플리트 트리의 모든 노드의 개수 = (분기계수^(깊이+1) - 1)/(분기계수-1) 로 구할 수 있다.
예 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의 노드를 루트로 하는 또 다른 하나의 컴플리트 트리로 생각하여 위의 공식을 반복하면 된다.

== 코드 ==
#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;
}

CompleteTreeLabeling/하기웅 - Revision history

Maintenance script: Repair batch-0001 pages from live compare

imported>Unknown at 05:22, 7 February 2021