一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1, d2, …, dn,编程需要输出满足d(vi)=di的树的个数。
建筑保温板,灵宇,yy2014年度盛典排名
一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1, d2, …, dn,编程需要输出满足d(vi)=di的树的个数。
第一行是一个正整数n,表示树有n个结点。第二行有n个数,第i个数表示di,即树的第i个结点的度数。其中1<=n<=150,输入数据保证满足条件的树不超过10^17个。
输出满足条件的树有多少棵。
答案为
上面是整棵树的排列方案
下面是每个点重复的方案
一边除乘一边除
// luogu-judger-enable-o2 #include<cstdio> #define int long long using namespace std; const int MAXN = 10005; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-')f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int inder[MAXN], N, sum = 0; int js[MAXN]; main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif N = read(); js[0] = js[1] = 1; for(int i = 1; i <= 150; i++) js[i] = js[i-1] * i; for(int i = 1; i <= N; i++) { inder[i] = read(); sum += inder[i] - 1; if(inder[i] == 0 && N != 1) {printf("0");return 0;} } if(sum != N - 2) {printf("0");return 0;} int Now = 1, times = 1; for(int i = 1; i <= N - 2; i++) { Now *= i; if(times > N) break; if(Now % js[ inder[times] - 1 ] == 0) Now /= js[ inder[times] - 1], times++; } printf("%lld",Now); return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论