本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-08 16:38:32

:::::info[题目基本信息] 考察：构造，哈希 hashing（$2900$）。
题目简介：
给定 $n$，有一集合 $\displaystyle S=\bigcup_{i=1}^n\{i\}$，问 $S$ 的最大子集 $S'$ 满足 $\displaystyle\prod_{x\in S'}x!\in\{p|p=k^2,k\in\mathbb Z\}$ 的大小，并给出一种 $S'$。
数据范围：

• $1\le n\le 10^6$

时间限制：4s。
空间限制：250MB。
::::: 结论：答案下界为 $n-3$。
:::::success[证明] 考虑凑平方。
$$\begin{aligned}\prod_{i=1}^ni!&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!(2i)!)\times([n\equiv 1\pmod 2]\cdot n)!\&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!^2)\times(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}2i)\times([n\equiv 1\pmod 2]\cdot n)!\&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!^2)\times 2^{\lfloor\frac{n}{2}\rfloor}\lfloor\frac{n}{2}\rfloor!\times([n\equiv 1\pmod 2]\cdot n)!\&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!^2)(2^{\lfloor\frac{n}{4}\rfloor})^2\times 2\lfloor\frac{n}{2}\rfloor!\times([n\equiv 1\pmod 2]\cdot n)!\end{aligned}$$ 我们开始丢数，当 $n$ 是奇数的时候，我们丢掉 $n!$，然后我们丢掉 $2!$ 和 $\lfloor\dfrac{n}{2}\rfloor!$，最后一定剩下一个完全平方数。
证毕。
::::: 这时我们仅需判断子集大小为 $n,n-1,n-2$ 时是否有解即可。

• 大小为 $n$ 时：容易发现此时对于每一个质数，它总共出现了偶数次，那么我们可以考虑异或哈希，给每一个质数附一个随机值，然后这些数的乘积的哈希值就是它们的异或和，这样可以计算出每个数的阶乘的哈希值，进而计算出整个序列的哈希值，此时哈希值为 $0$。
• 大小为 $n-1$ 时：同上，此时扔去一个数的哈希值为 $0$，即整个数列的哈希值等于某个数。
• 大小为 $n-2$ 时，同上，此时可以使用 map 处理。

这样就做完了。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

code