BZOJ1005明明的烦恼 Prufer + 分解質因數 + 高精度

@[高精度, Prufer, 質因數分解]

Description

自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在

任意两点间连线,可产生多少棵度数满足要求的树?

Input

第一行为$N(0 < N <= 1000)$,

接下来$N$行,第$i + 1$行给出第$i$个节点的度数$D_i$,如果对度数不要求,则输入$- 1$

Output

　　一个整数,表示不同的满足要求的树的个数,无解输出$0$

Sample Input

Sample Output

HINT

　　两棵树分别为1-2-3; 1-3-2

Solution

Prufer編碼的簡單應用.

Prufer是無根樹的一種編碼, 可以和無根樹之間形成一一對應關係. 生成Prufer編碼的方法很簡單, 大致過程如下(這都不是重點)

重點在於: 在Prufer編碼中, $$一個節點出現的次數 = 該點的度 - 1$$

有了這個性質, 這題就可以簡單地轉化為求Prufer編碼的排列組合數量.

實際上就是用分解質因數的方法來優化, 然後再用高精度計算最終答案.

#include<cstdio>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	int x = 0, flag = 1;

	char c;

	while(! isdigit(c = getchar()))

		if(c == '-')

			flag *= - 1;

	while(isdigit(c))

		x = x * 10 + c - '0', c = getchar();

	return x * flag;

}

void println(int x)

{

    if(x < 0)

        putchar('-'), x *= - 1;

    if(x == 0)

        putchar('0');

    int ans[10], top = 0;

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const int N = 1 << 10;

int top;

int isprime[N], prime[N];

void get_prime()

{

	memset(isprime, - 1, sizeof(isprime));

	top = 0;

	for(int i = 2; i < N; i ++)

		if(isprime[i] == - 1)

		{

			isprime[i] = 1, prime[top ++] = i;

			for(int j = i << 1; j < N; j += i)

				isprime[j] = 0;

		}

}

int ans[N];

void C(int n, int m)

{

	for(int i = n; i > n - m; i --)

	{

		int p = i;

		for(int j = 0; j < top; j ++)

			while(! (p % prime[j]))

				ans[j] ++, p /= prime[j];

	}

	for(int i = m; i; i --)

	{

		int p = i;

		for(int j = 0; j < top; j ++)

			while(! (p % prime[j]))

				ans[j] --, p /= prime[j];

	}

}

struct Giant

{

	int dig[1 << 20];

	int top;

	Giant()

	{

		top = 1;

		memset(dig, 0, sizeof(dig));

		dig[0] = 1;

	}

};

void operator *(Giant &x, int y)

{

	for(int i = 0; i < x.top; i ++)

		x.dig[i] *= y;

	for(int i = 0; i < x.top; i ++)

		if(x.dig[i] > 9)

			x.dig[i + 1] += x.dig[i] / 10, x.dig[i] %= 10;

	while(x.dig[x.top])

		x.dig[x.top + 1] = x.dig[x.top] / 10,

		x.dig[x.top] %= 10,

		x.top ++;

}

void println(Giant &x)

{

	for(int i = x.top; i; i --)

		putchar(x.dig[i - 1] + '0');

	putchar('\n');

}

Giant Ans;

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("BZOJ1005.in", "r", stdin);

	freopen("BZOJ1005.out", "w", stdout);

	#endif

	get_prime();

	int n = read();

	int len = 0, cnt = 0;

	//len記錄prufer序列已經佔用的長度, cnt記錄尚未確定度的點數

	for(int i = 0; i < n; i ++)

	{

		int D = read();

		if((! D) || (D - 1 + len > n - 2))

		{

			println(0);

			return 0;

		}

		if(D == - 1)

			cnt ++;

		if(D > 0)

			C(n - 2 - len, D - 1), len += D - 1;

	}

	if(len < n - 2)

	{

		for(int i = 0; i < top; i ++)

			while(! (cnt % prime[i]))

				ans[i] += n - 2 - len, cnt /= prime[i];

	}

	for(int i = 0; i < top; i ++)

		for(int j = 0; j < ans[i]; j ++)

			Ans * prime[i];

	println(Ans);

}