题目链接
bzoj1211: [HNOI2004] 树的计数 https://www.lydsy.com/JudgeOnline/problem.php?id=1211
题解
prufer 序
可重排列计数
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- int n = 0;
- int b[10007];
- int cnt[10007];
- void Div(int x,int k = 1) {
- for(int j = 2;j * j <= x;++ j) {
- while(x % j == 0) {
- cnt[j] += k;
- x /= j;
- }
- }
- cnt[x] += k;
- }
- main() {
- int tot = 0;
- scanf("%lld",&n);
- for(int i = 1;i <= n;++ i) {
- scanf("%lld",&b[i]);
- if(!b[i] && n> 1) {
- puts("0");return 0;
- }
- tot += b[i];
- }
- if(tot - n != n -2 ) {
- puts("0"); return 0;
- }
- if(n <= 2) {puts("1"); return 0; }
- for(int i = 2;i <= n - 2; ++ i) Div(i);
- for(int i = 1;i <= n;++ i) {
- for(int j = 2;j < b[i];++ j) Div(j,-1);
- }
- long long ans = 1;
- for(int i = 1;i <= n;++ i)
- for(int j = 1;j <= cnt[i];++ j) ans *= i;
- cout << ans <<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2691928.html