1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 6664 Solved: 2626 [Submit][Status][Discuss] Description 自从明明学了树的结构,就对奇怪的树产生了兴趣…给出标号为1到N的点,以及某些点最终的度数,允许在 任意两点间连线,可产生多少棵度数满足要求的树?
Input 第一行为N(0 < N < = 1000), 接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output 一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input 3
1
-1
-1 Sample Output 2 HINT 两棵树分别为1-2-3;1-3-2
Source
先粘一波其它博主的blog吧… https://blog.csdn.net/jiangshibiao/article/details/22651081 其实我们还是利用prufer数列与树的一一对应关系，然后我们就可以利用排列组合来求了 AC Code:
#include<bits/stdc++.h> #define rg register #define il inline #define maxn 3000010 #define ll long long #define eps 1e-8 using namespace std; il int read(){rg int x = 0 , w = 1 ; rg char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') w = -1; ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + ch - '0' ; ch = getchar();}return x * w;} int q[maxn << 1] , tot , rnx[maxn] , a[maxn] , b[maxn] , c[maxn] , val[maxn] , primes[maxn]; int flag[maxn] , p[maxn] , delta; bool vis[maxn]; void prime(int n){ vis[1] = 1; for (rg int i = 2 ; i <= n ; ++i){ if (!vis[i]) { primes[++tot] = i; rnx[i] = tot; } for (rg int j = 1 ; j <= tot && i * primes[j] <= n; ++j){ vis[i * primes[j]] = 1; if (!(i % primes[j])) break; } } } void fenjie(int x){ delta += p[x]; rg int tmp = x , i = 1; if (!vis[x]){ val[rnx[x]] += delta; return; } while (vis[tmp] && tmp != 1){ while (!(tmp % primes[i])){ val[i] += delta; tmp /= primes[i]; } ++i; } if (tmp != 1) val[rnx[tmp]] += delta; } int main(){ prime(500000); int n = read() , x , res = 0 , cnt = 0 , sum = 0; for (rg int i = 1 ; i <= n ; ++i){ x = read(); if (x > 0){ q[++cnt] = x; sum += x - 1; } else if (x == 0){ puts("0"); return 0; } else ++res; } if (sum > (2 * n - 2)){ puts("0"); return 0; } rg int maxr = -1; maxr = max(maxr , n - 1); p[1]++; p[n - 1]--; p[1]--; p[n - 1 - sum]++; for (rg int i = 1 ; i <= cnt ; ++i){ p[1]--; p[q[i]]++; maxr = max(q[i] , maxr); } p[res] += n - 2 - sum; p[res + 1] -= n - 2 - sum; maxr = max(res + 1 , maxr); for (rg int i = 1 ; i <= 200005; ++i){ fenjie(i); } rg int len = 1; a[len] = 1; for (rg int i = 1 ; i <= 1000 ; ++i){ if (!val[i]) continue; for (rg int j = 1 ; j <= val[i] ; ++j){ int xx = primes[i]; x = 0; for (rg int k = 1 ; k <= len ; ++k){ a[k] = a[k] * xx + x; x = a[k] / 10; a[k] = a[k] % 10; } while(x > 0){ a[++len] = x % 10; x /= 10; } } } for (rg int i = len ; i >= 1 ; --i) printf("%d" , a[i]); return 0; }