BZOJ 1211[HNOI2004]树的计数 - prufer数列

描述

一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，编程需要输出满足d(vi)=di的树的个数。

题解

每颗树都对应以中prufer数列， prufer数列中数出现的个数 $=$ 节点的度数 -1

所以变成了求再prufer数列中， $x$出现次数为$c_x$ 的排列数

答案为$!(N - 2) / \prod\limits_{i = 1}^N{a_i-1}$

直接算会爆LL， 需要分解质因数

另外还需要特判

代码

我发现打了个错误程序，由于某B姓OJ数据太水竟然过了。。。这个是错误的→_→，幸好发现了， 不然要出锅QAQ

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 #define rd read()

 using namespace std;

 const int N = ;

 int pri[N], tot, vis[N], n, cnt[N], sum;

 ll ans = ;

 ll fpow(ll a, ll p) {

     ll re = ;

     for(; p; p >>= , a = a * a) if(p & ) re = re * a;

     return re;

 }

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X  *  + c - '';

     return X * p;

 }

 void init() {

     for(int i = ; i < N; ++i) {

         if(!vis[i]) pri[++tot] = i;

         for(int j = ; j <= tot && pri[j] * i < N; ++j) {

             vis[i * pri[j]] = ;

             if(i % pri[j] == ) break;

         }

     }

 }

 void cal(int x, int k) {

     if(!x || x == ) return;

     for(int i = ; i <= tot && x != ; ++i) if(x % pri[i] == ) {

         while(x % pri[i] == ) cnt[i] += k, x /= pri[i];

     }

 }

 int main()

 {

     init();

     n = rd;

     for(int i = ; i <= n - ; ++i) cal(i, );

     for(int i = ; i <= n; ++i) {

         int x = rd;

         if(n !=  && !x) return printf("0\n"), ;

         if(n ==  && x) return printf("0\n"), ;

         if(n ==  && !x) return printf("1\n"), ;

         for(int j = ; j < x; ++j) cal(j, -);

         sum += x - ;

     }

     if(sum != n - ) return printf("0\n"), ;

     for(int i = ; i <= tot; ++i) ans *= fpow(pri[i], cnt[i]);

     printf("%lld\n", ans);

 }