CF1622F Quadratic Set 题解
zrl123456
·
·
题解
:::::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'。
数据范围：
时间限制：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