bzoj1211: [HNOI2004]树的计数 prufer编码

题目链接

bzoj1211: [HNOI2004]树的计数

题解

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; 
}