题目链接: https://www.luogu.org/problemnew/show/P2624

0 前置技能

• Prufer 序列

1 推式子时间

这个题目很像 Luogu P2290

但是问题在于，这个里面具有不确定的度数

经过简单的思考，我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中

• $sum$ 为已知总度数
• $cnt$ 为已知点数

我们分两段解释
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!}
$$
这一段是将已经有的放到 Prufer 序列中的方案数
$$
(n – cnt) ^{n – sum – 2}
$$
剩下 $n – cnt$ 个点，可以放在剩下的所有位置（共$n – sum – 2$）中

然后化简一下式子
$$
\frac{(n-2)!}{(n-sum-2)\times \prod_{i=1}^{cnt}(d_i-1)!}\times (n-cnt)^{n-sum-2}
$$
高精度警告

2 代码

#include <cstdio>
#include <cstring>

const int BASE = 10;

struct Bigint {
    int num[11000], cnt;
    Bigint() {
        cnt = 0;
        memset(num, 0, sizeof(num));
    }
    int& operator[] (int now) { return num[now]; }
    void operator*= (int now) {
        for(int i = 1; i <= cnt; i ++)
            num[i] *= now; 
        for(int i = 1; i <= cnt; i ++){
            if( num[i] >= BASE ) {
                num[i + 1] += num[i] / BASE;
                num[i] %= BASE;
            }
        }
        while(num[cnt + 1] != 0){
            cnt ++;
            if( num[cnt] >= BASE ) {
                num[cnt + 1] += num[cnt] / BASE;
                num[cnt] %= BASE;
            }
        }
    }
    void operator/= (int now){
        for(int i = cnt; i; i --){
            num[i - 1] += (num[i] % now * 10);
            num[i] /= now;
        }
        while( !num[ cnt ] )
            cnt --;
    }
    void to_bigint(int now) {
        while(now) {
            num[ ++ cnt ] = now % BASE;
            now /= BASE;
        }
    }
    void print(char end = 0) {
        for(int i = cnt; i; i --)
            printf("%d", num[i]);
        end && putchar(end);
    }
};

int main() {
#ifdef woshiluo
    freopen("luogu.2624.in", "r", stdin);
    freopen("luogu.2624.out", "w", stdout);
#endif
    int n, d[1100], cnt = 0, sum = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &d[i]);
        if(d[i] == -1)
            continue;
        cnt ++; sum += d[i] - 1;
    }
    Bigint ans; ans.to_bigint(1);
    for(int i = n - 1 - sum; i < n - 1; i++)
        ans *= i;
    for(int i = 1; i <= n - 2 - sum; i++)
        ans *= (n - cnt);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j < d[i]; j++)
            ans /= j;
    ans.print();
}