【BZOJ 1211】[HNOI2004] 树的计数

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1211
数据生成器:http://paste.ubuntu.com/23338142/

这题知道prufer编码的人做起来是大水题吧?
可以搞一搞组合数,或者直接上可重集的全排列?

#include<bits/stdc++.h>
#define LL long long
using namespace std; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int C(const int &a, const int &b) {
	static int ret; ret = 1;
	for (int i=1;i<=b;i++) ret *= i;
	for (int i=1;i<=a;i++) ret /= i;
	for (int i=1;i<=b-a;i++) ret /= i;
	return ret;
}

int main(){
	int n=read();
	if (n == 1) {
		if (read() == 0) puts("1");
		else puts("0"); 
	} else if (n == 2) {
		if (read() == 1 && read() == 1) puts("1");
		else puts("0");
	} else {
		n -= 2; LL vout = 1;
		for (int i=n+2,tmp;i;i--) {
			vout *= C(tmp=read()-1,n);
			n -= tmp;
		}
		if (n == 0) cout<<vout;
		else puts("0");
	}
	return 0;
}

2 thoughts to “【BZOJ 1211】[HNOI2004] 树的计数”

  1. Hey there just wanted to give you a quick heads up and let you know a few of the images aren’t loading correctly. I’m not sure why but I think its a linking issue. I’ve tried it in two different internet browsers and both show the same results.

Leave a Reply

Your email address will not be published. Required fields are marked *