BZOJ 1005 明明的烦恼
Description
自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
Input
第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output
一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input
3
1
-1
-1
1
-1
-1
Sample Output
2
HINT
两棵树分别为1-2-3;1-3-2
利用Purfer Sequence，参见：http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html
1 #include<cstring> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 6 #define maxn 1010 7 int d[maxn],n,sum,cnt,tot,prime[maxn],num[maxn]; 8 bool exist[maxn]; 9 struct node 10 { 11 int a[maxn*10],len; 12 node(){memset(a,0,sizeof(a)); len = 1;} 13 friend inline node operator *(node &x,int y) 14 { 15 node z; z.len = x.len + 3; 16 int i; 17 for (i = 1;i <= z.len;++i) 18 { 19 z.a[i] += x.a[i] * y; 20 z.a[i+1] += z.a[i] / 10; 21 z.a[i] %= 10; 22 } 23 while (!z.a[z.len]) --z.len; 24 return z; 25 } 26 27 inline void print() {for (int i = len;i;--i) printf("%d",a[i]);} 28 }ans; 29 30 inline void ready() 31 { 32 int i,j; 33 for (i = 2;i <= 1000;++i) 34 if (!exist[i]) 35 { 36 exist[i] = true; 37 prime[++tot] = i; 38 for (j = i*i;j <= 1000;j += i) 39 exist[j] = true; 40 } 41 } 42 43 inline bool okay() 44 { 45 for (int i = 1;i <= n;++i) 46 { 47 if (d[i] > 0) sum += d[i] - 1,++cnt; 48 if (d[i] == 0) return false; 49 } 50 if (sum + n - cnt > 2*(n-1)) return false; 51 if (cnt == n && sum != 2*(n-1)) return false; 52 return true; 53 } 54 55 inline void Div(int a,int bei) 56 { 57 if (a == 0) return; 58 if (bei == 0) return; 59 for (int i = 1;i <= tot;++i) 60 { 61 if (a == 1) break; 62 if (a % prime[i] == 0) 63 { 64 int t = 0; 65 while (a % prime[i] == 0) ++t,a /= prime[i]; 66 num[i] += t * bei; 67 } 68 } 69 } 70 71 inline void calc() 72 { 73 ready(); 74 for (int i = 1;i <= n-2;++i) Div(i,1); 75 Div(n - cnt,n-sum-2); 76 for (int i = 1;i <= n-2-sum;++i) Div(i,-1); 77 for (int i = 1;i <= n;++i) if (d[i] != -1) 78 for (int j = 1;j < d[i];++j) Div(j,-1); 79 ans.a[1] = 1; 80 for (int i = 1;i <= tot;++i) 81 for (int j = 1;j <= num[i];++j) 82 ans = ans * prime[i]; 83 ans.print(); 84 } 85 86 int main() 87 { 88 scanf("%d",&n); int i; 89 for (i = 1;i <= n;++i) scanf("%d",d+i); 90 if (!okay()) printf("%d",0); 91 else calc(); 92 return 0; 93 }