题目描述
给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
输入
第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
输出
一个整数,表示不同的满足要求的树的个数,无解输出0
样例输入
3 1 -1 -1
样例输出
2
题解
Prufer序列+高精度
Prufer序列：由一棵 $n$ 个点的树唯一产生的一个 $n-2$ 个数的序列。
生成方法：找到这棵树编号最小的叶子节点，将其相邻点加入到序列中，删掉这个点。重复这个过程直到树中只剩下两个点，此时得到的序列即为该树的Prufer序列。
性质：任何一个长度为 $n-2$ ，每个数均在 $1\sum n$ 之间的序列均为一个合法的Prufer序列，对应且只对应着一棵 $n$ 个点的树。
性质：在原树中度数为 $d$ 的点，在Prufer序列中出现了 $d-1$ 次。
根据这两个性质可以考虑本题。给出了每个点的度数限制，即给出了每个点在Prufer序列中出现的次数。对于没给限制的，可以随意选择。
相当于先在 $n-2$ 个数中选出一部分作为没有限制的，剩下的是有限制的。
对于没有限制的，答案就是 $没限制的位置个数^没限制的点的个数$ 。
对于有限制的，使用组合数学的一个公式：长度为 $\sum a_i$ 的序列，第 $i$ 个数出现了 $a_i$ 次的序列数为 $\frac{(\sum a_i)!}{\prod(a_i!)}$ 。
本题不取模，为避免高精度除法，将阶乘分解质因数来处理。
注意特判无解的情况。
#include#include #include #define mod 100000000using namespace std;typedef long long ll;struct data{ int len; ll v[400]; ll &operator[](int a) {return v[a];} data operator+(data &a) { data ans; memset(ans.v , 0 , sizeof(ans.v)); int i; for(i = 0 ; i < len || i < a.len || ans[i] ; i ++ ) ans[i] += v[i] + a[i] , ans[i + 1] = ans[i] / mod , ans[i] %= mod; ans.len = i; return ans; } data operator*(int a) { data ans; memset(ans.v , 0 , sizeof(ans.v)); int i; for(i = 0 ; i < len || ans[i] ; i ++ ) ans[i] += v[i] * a , ans[i + 1] = ans[i] / mod , ans[i] %= mod; ans.len = i; return ans; } void write() { int i; printf("%lld" , v[len - 1]); for(i = len - 2 ; ~i ; i -- ) printf("%08lld" , v[i]); puts(""); }}ans;int a[1010] , cnt[1010] , prime[1010] , tot , np[1010];void init(){ int i , j; for(i = 2 ; i <= 1000 ; i ++ ) { if(!np[i]) prime[++tot] = i; for(j = 1 ; j <= tot && i * prime[j] <= 1000 ; j ++ ) { np[i * prime[j]] = 1; if(i % prime[j] == 0) break; } }}void solve(int x , int a){ int i , j; for(i = 1 ; i <= tot ; i ++ ) for(j = x / prime[i] ; j ; j /= prime[i]) cnt[i] += a * j;}int main(){ init(); int n , i , c1 = 0 , c2 = 0; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) { scanf("%d" , &a[i]); if(a[i] > 0) c1 += a[i] - 1; else if(a[i] == -1) c2 ++ ; else { puts("0"); return 0; } } if(c1 > n - 2) { puts("0"); return 0; } solve(n - 2 , 1) , solve(n - 2 - c1 , -1); for(i = 1 ; i <= n ; i ++ ) if(a[i] > 0) solve(a[i] - 1 , -1); ans[0] = ans.len = 1; for(i = 1 ; i <= tot ; i ++ ) while(cnt[i] -- ) ans = ans * prime[i]; for(i = 1 ; i <= n - 2 - c1 ; i ++ ) ans = ans * c2; ans.write(); return 0;}