Luogu P2624 [HNOI2008] 明明的烦恼

qwq

首先给出度数 k 个点,当前 Prufer 序列总长 $sum = \sum \limits_{i = 1} ^ k (d_i - 1)$, 它对答案贡献为 $C_{n - 2} ^ {sum} \frac{sum!}{\prod \limits_{i = 1}^k (d_i - 1)!}$.

剩下的点填满 $n - sum - 2$ 个空位,贡献为 $(n - k) ^ {n - sum - 2}$.

最终答案:$C_{n - 2} ^ {sum} \frac{sum!}{\prod \limits_{i = 1}^k (d_i - 1)!} (n - k) ^ {n - sum - 2}$.

化简:$\frac{(n - 2)!}{ (n - sum - 2)! \prod \limits_{i = 1}^k (d_i - 1)!} (n - k) ^ {n - sum - 2}$

数太大啦,用质因数分解 + BigInt 求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>

int n, d[1005], QAQ, pri[1005], mip[1005], cnt[1005][1005], fin[1005], sum;

void init(int t) {
for (int i = 2; i <= t; i++) {
if (!mip[i]) mip[i] = i, pri[++pri[0]] = i;
for (int j = 1; j <= pri[0] && i * pri[j] <= t; j++) {
mip[i * pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
for (int i = 2; i <= t; i++) {
for (int j = 1; j <= pri[0]; j++) {
int x = i;
while (x % pri[j] == 0) ++cnt[i][j], x /= pri[j];
cnt[i][j] += cnt[i - 1][j];
}
}
}

struct BigInt {
int l, a[23333], base;
BigInt() {
l = 0, base = 10;
memset(a, 0, sizeof(a));
}
BigInt Trans(int x) {
BigInt y;
while (x)
y.a[++y.l] = x % y.base, x /= y.base;
return y;
}
friend BigInt operator +(BigInt x, BigInt y) {
BigInt z;
z.l = std::max(x.l, y.l);
for (int i = 1; i <= z.l; i++)
z.a[i] = x.a[i] + y.a[i], z.a[i + 1] += z.a[i] / x.base, x.a[i] %= x.base;
if (z.a[z.l + 1]) z.l++;
return z;
}
friend BigInt operator +(BigInt x, int y) {
BigInt tmp = tmp.Trans(y);
return x + tmp;
}
friend BigInt operator -(BigInt x, BigInt y) {
BigInt z;
z.l = std::max(x.l, y.l);
for (int i = 1; i <= z.l; i++) {
if (x.a[i] < y.a[i]) x.a[i] += x.base, x.a[i + 1]--;
z.a[i] = x.a[i] - y.a[i];
}
while (!z.a[z.l] && z.l) z.l--;
if (z.l == 0) z.a[1] = 1, z.l = 1;
return z;
}
friend BigInt operator *(BigInt x, BigInt y) {
BigInt z;
z.l = x.l + y.l;
if ((x.l == 1 && x.a[1] == 0) || (y.l == 1 && y.a[1] == 0)) {
z.l = 1;
return z;
}
for (int i = 1; i <= x.l; i++)
for (int j = 1; j <= y.l; j++)
z.a[i + j - 1] += x.a[i] * y.a[j], z.a[i + j] += z.a[i + j - 1] / x.base, z.a[i + j - 1] %= x.base;
while (!z.a[z.l] && z.l) z.l--;
if (!z.l) {z.l = 1, z.a[1] = 0;}
return z;
}
friend BigInt operator *(BigInt x, int y) {
BigInt z; int l = x.l;
for (int i = 1; i <= l; i++)
z.a[i] += x.a[i] * y, z.a[i + 1] += z.a[i] / x.base, z.a[i] %= x.base;
while (z.a[l + 1])
l++, z.a[l + 1] += z.a[l] / x.base, z.a[l] %= x.base;
z.l = l;
while (!z.a[z.l]) z.l--;
return z;
}
friend BigInt operator /(BigInt x, int y) {
BigInt z; z.l = x.l;
int t = 0;
for (int i = x.l; i >= 1; i--)
t = t * 10 + x.a[i], z.a[i] = t / y, t %= y;
while (!z.a[z.l]) z.l--;
return z;
}
void print() {
for (int i = l; i >= 1; i--)
printf("%d", a[i]);
printf("\n");
}
};

BigInt Qpow(int x, int p) {
BigInt ret = ret.Trans(1), tmp = tmp.Trans(x);
for (; p; p >>= 1, tmp = tmp * tmp)
if (p & 1) ret = ret * tmp;
return ret;
}

signed main() {
scanf("%d", &n);
init(1000);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
if (x != -1) d[++QAQ] = x, sum += x - 1;
}
BigInt ans = ans.Trans(1);
ans = ans * Qpow(n - QAQ, n - 2 - sum);
for (int i = 1; i <= pri[0]; i++) {
fin[i] += cnt[n - 2][i] - cnt[n - sum - 2][i];
for (int j = 1; j <= QAQ; j++)
fin[i] -= cnt[d[j] - 1][i];
}
for (int i = 1; i <= pri[0]; i++)
ans = ans * Qpow(pri[i], fin[i]);
ans.print();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×