自动搬运

查看原文

来自洛谷，原作者为

	EternalEpic 一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程。

搬运于2025-08-24 21:39:46，当前版本为作者最后更新于2020-10-04 11:20:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

设有 $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;
}

/**/