首页 > 代码库 > BZOJ 1005 明明的烦恼

BZOJ 1005 明明的烦恼

2024-10-29 22:22:39   211人阅读

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

 

利用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 node10 {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 }
View Code

 

BZOJ 1005 明明的烦恼


联系
我们