[BZOJ]1005 [HNOI2008]明明的烦恼

题意

一棵树，给定每个点的度数，\(-1\)为无限制，求满足该度数的树的个数。

题解

prufer序列的裸题。
关于prufer序列，网上有更加详细的介绍，这里就不展开说明了，只介绍跟该题相关的性质。

所有无根树可以跟prufer序列形成双射。
一棵无根树，每个点在prufer序列出现的次数为它的度数减一。

这道题显然只要确定有度数限制的那些点，剩下的点任取即可。
记每个点的度数限制为\(d[i]\)，\(cnt\)为没有度数限制的点的个数

\[ans = \frac{A(n - 2, \sum (d[i] - 1))}{\Pi A(d[i] - 1)} \times cnt ^ {n - 2 - \sum (d[i] - 1)} \]

这道题需要高精度，但是普通的高精度仍然不够，因为组合数增长是\(n!\)级别的。
但是显然答案的长度不会很长。
于是可以记录指数来先进行乘除运算，最后再统一计算答案。
质因数分解每个要乘的数即可。

注意判断无解的情况，即度数减一之和大于序列长度 或者 有点的度数为0但是n不为1。

(BZOJ的题真的是每道题都有收获)

#include 
#include 
#include 
#include 
#include 
#include 
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)

using namespace std;

int read(){
	char c; int num, f = 1;
	while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
	while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
	return f * num;
}
const int N = 5009;
int n, d[N], cnt, res, pri[N], ans[N], len = 1;
void update(int x, int f) {
	for(int i = 2; i * i <= x; i++) while(x % i == 0) {
		pri[i] += f;
		x /= i;
	}
	if(x > 1) pri[x] += f;
}
int A(int n, int m, int f) {
	for(int i = n; i > n - m; i--)
		update(i, f);
}
void times(int x) {
	for(int i = 1; i <= len; i++) ans[i] *= x;
	for(int i = 1; i < len; i++) {
		ans[i + 1] += ans[i] / 10;
		ans[i] %= 10;
	}
	while(ans[len] >= 10) {
		ans[len + 1] = ans[len] / 10;
		ans[len] %= 10;
		len++;
	}
}
void print() {
	for(int i = len; i; i--)
		printf("%d", ans[i]);
}
signed main()
{
	n = read();
	for(int i = 1; i <= n; i++) {
		d[i] = read();
		if(d[i] == -1) cnt++;
		else {
			if(d[i] == 0) {
				if(n == 1) printf("1\n");
				else printf("0\n");
				return 0;
			}
			d[i]--;
			res += d[i];
		}
	}
	if(res > n - 2) {
		printf("0\n");
		return 0;
	}
	ans[1] = 1;
	A(n - 2, res, 1);
	for(int i = 1; i <= n; i++) 
		if(d[i] != -1) 
			A(d[i], d[i], -1);
	for(int i = 2; i <= 1000; i++)
		for(int j = 1; j <= pri[i]; j++)
			times(i);
	for(int i = 1; i <= n - 2 - res; i++)
		times(cnt);
	print();
	return 0;
}
题解Prufer序列

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签