题解 P2624 【[HNOI2008]明明的烦恼】

· · 题解

目前最优解，比第二名快一倍。

设有 cnt 个点度数已知。

我们可以知道 Prufer 序列中已经占有的位置数 sum=\sum_{i=1}^{n}\left(deg_{i}-1\right)

根据 Cayley 公式和组合我们可以知道，这些有明确 deg 的点的排列方案数为

C_{n-2}^{s u m} \times \frac{s u m !}{\prod_{i=1}^{c n t}\left(deg_{i}-1\right) !}

最后剩余的 (n - cnt) 个数任意插入在 (n - sum - 2) 个位置上，所以要乘 (n - cnt)^{n - sum - 2}

可以预处理阶乘的质因数指数避免前半部分的高精度除法，但求答案还是要用高精度乘法，这里笔者采用压八位的高精。

const int Maxn = 1e3 + 5;
int tot = 0, prime[Maxn]; bool vis[Maxn];
inline void sieve(void) {
    vis[1] = true;
    for (int i = 2; i <= 1000; i++) {
        if (!vis[i]) prime[++tot] = i;
        for (int j = 1; j <= tot && i * prime[j] <= 1000; j++) {
            vis[i * prime[j]] = true; if (i % prime[j] == 0) break;
        }
    }
}

inline int rate(int n, int p) {
    int ret = 0;
    while (n) {
        ret += n / p;
        n /= p;
    } return ret;
}

int ps[Maxn];
inline void calc(int n, int typ) {
    for (int i = 1; i <= tot; i++)
        ps[i] += typ * rate(n, prime[i]);
}

int n, deg[Maxn], sum = 0, cnt = 0;
const int mod = 100000000;
inline vector <int> Multiply(vector <int> vec, int rec) {
    vector <int> ret; ll t = 0ll; ret.clear();
    for (int i = 0; i < vec.size(); i++) {
        t += 1ll * vec[i] * rec;
        ret.push_back(t % mod); t /= mod;
    } while (t) { ret.push_back(t % mod); t /= mod; }
    return ret;
}

signed main(void) {
    read(n); vector <int> ret(1, 1); sieve();
    for (int i = 1; i <= n; i++) {
        read(deg[i]);
        if (deg[i] != -1) sum += deg[i] - 1, ++cnt;
    } calc(n - 2, 1); calc(n - 2 - sum, -1);
    for (int i = 1; i <= n; i++) if (deg[i] != -1) calc(deg[i] - 1, -1);
    for (int i = 1; i <= tot; i++)
    for (int j = 1; j <= ps[i]; j++) ret = Multiply(ret, prime[i]);
    for (int i = 1; i <= n - 2 - sum; i++) ret = Multiply(ret, n - cnt);
    write(ret[ret.size() - 1]);
    for (int i = (int)(ret.size()) - 2; i >= 0; i--) {
        if (ret[i] < 10) printf("0000000");
        else if (ret[i] < 100) printf("000000");
        else if (ret[i] < 1000) printf("00000");
        else if (ret[i] < 10000) printf("0000");
        else if (ret[i] < 100000) printf("000");
        else if (ret[i] < 1000000) printf("00");
        else if (ret[i] < 10000000) printf("0");
        write(ret[i]);
    }
    return 0;
}

/**/