首页 > 代码库 > BZOJ 1005 明明的烦恼
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 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 }
BZOJ 1005 明明的烦恼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。