[Dangerous Data - 题目 - QOJ.ac](https://qoj.ac/contest/3773/problem/18404) ## 解法一 最自然的一种思路，首先我们要先找到一个 $(10^6,2^{20})$ 之间的质数 $P$，以下操作都在模 $P$ 意义下 维护全集所有数字的 $1$ 到 $k$ 次方和，即 $$ \begin{aligned} p_1 &= x_1 + x_2 + \dots + x_{n+k} \\ p_2 &= x_1^2 + x_2^2 + \dots + x_{n+k}^2 \\ &\dots \\ p_k &= x_1^k + x_2^k + \dots + x_{n+k}^k \end{aligned} $$ 解密时减去已知的数的 $1$ 到 $k$ 次方和，得到缺失集合 $A$ 的各次幂和。 利用牛顿恒等式，在 $\mathcal{O}(k^2)$ 的时间内将幂和 $p_i$ 转化为初等对称多项式 $e_i$，即可还原出方程 $$ x^k - e_1 x^{k-1} + e_2 x^{k-2} - e_3 x^{k-3} + \dots + (-1)^k e_k \equiv 0 \pmod P $$ 该方程即为 $$ (x-a_1)(x-a_2)\cdots(x-a_k)=0 $$ $a_i$ 为缺失的数，然后试根解出即可 ## 解法二 这是题解给出的做法 我们需要记录的 $k$ 个数为： - $\sum_{x \in S} x$ - $\sum_{x,y \in S, x<y} x \cdot y$ - ...直至选 $k$ 个数相乘的和。 第一次交互时可以直接使用背包计算，设 $f_j$ 为选 $j$ 个数相乘的和，初始 $f_0=1$。 倒序遍历 $$ f_j = (f_j + f_{j-1} \cdot x) \pmod P $$ 将算出的 $f_1 \dots f_k$ 记录 利用该 DP 的可逆性剔除已知的 $n$ 个数，对于每个已知数 $x$，**正序**遍历以撤销其影响： $$ f_j = (f_j - f_{j-1} \cdot x \pmod P + P) \pmod P $$ 全部撤销后，剩下的 $f$ 数组就是缺失集合构成的方程系数，直接跑试根即可。 ## 解法三 将集合内的数字看作多项式 $P(x) = \prod_{a_i \in S} (x+a_i)$。 记录该多项式在 $x = 1, 2, \dots, k$ 这 $k$ 个位置的点值。 解密时，先除以已知的 $n$ 个数构成的点值，得到缺失多项式的前 $k$ 个点值： $$ R(x)= \prod_{a_i \in A} (x+a_i) $$ 发现 $R(x)$ 是 $k$ 次多项式，最高次项系数为 $1$，其第 $k$ 阶差分为常数 $k!$。 已知 $R(x)$ 前 $k$ 项及对应的 $k$ 阶差分，即可推出所有项，找到 $R(x)=0$ 的根后即可直接还原。 这是这道题的超级加强版： [Problem - J - Codeforces](https://codeforces.com/gym/106626/problem/J) Loading... [Dangerous Data - 题目 - QOJ.ac](https://qoj.ac/contest/3773/problem/18404) ## 解法一 最自然的一种思路，首先我们要先找到一个 $(10^6,2^{20})$ 之间的质数 $P$，以下操作都在模 $P$ 意义下 维护全集所有数字的 $1$ 到 $k$ 次方和，即 $$ \begin{aligned} p_1 &= x_1 + x_2 + \dots + x_{n+k} \\ p_2 &= x_1^2 + x_2^2 + \dots + x_{n+k}^2 \\ &\dots \\ p_k &= x_1^k + x_2^k + \dots + x_{n+k}^k \end{aligned} $$ 解密时减去已知的数的 $1$ 到 $k$ 次方和，得到缺失集合 $A$ 的各次幂和。 利用牛顿恒等式，在 $\mathcal{O}(k^2)$ 的时间内将幂和 $p_i$ 转化为初等对称多项式 $e_i$，即可还原出方程 $$ x^k - e_1 x^{k-1} + e_2 x^{k-2} - e_3 x^{k-3} + \dots + (-1)^k e_k \equiv 0 \pmod P $$ 该方程即为 $$ (x-a_1)(x-a_2)\cdots(x-a_k)=0 $$ $a_i$ 为缺失的数，然后试根解出即可 ## 解法二 这是题解给出的做法 我们需要记录的 $k$ 个数为： - $\sum_{x \in S} x$ - $\sum_{x,y \in S, x<y} x \cdot y$ - ...直至选 $k$ 个数相乘的和。 第一次交互时可以直接使用背包计算，设 $f_j$ 为选 $j$ 个数相乘的和，初始 $f_0=1$。 倒序遍历 $$ f_j = (f_j + f_{j-1} \cdot x) \pmod P $$ 将算出的 $f_1 \dots f_k$ 记录 利用该 DP 的可逆性剔除已知的 $n$ 个数，对于每个已知数 $x$，**正序**遍历以撤销其影响： $$ f_j = (f_j - f_{j-1} \cdot x \pmod P + P) \pmod P $$ 全部撤销后，剩下的 $f$ 数组就是缺失集合构成的方程系数，直接跑试根即可。 ## 解法三 将集合内的数字看作多项式 $P(x) = \prod_{a_i \in S} (x+a_i)$。 记录该多项式在 $x = 1, 2, \dots, k$ 这 $k$ 个位置的点值。 解密时，先除以已知的 $n$ 个数构成的点值，得到缺失多项式的前 $k$ 个点值： $$ R(x)= \prod_{a_i \in A} (x+a_i) $$ 发现 $R(x)$ 是 $k$ 次多项式，最高次项系数为 $1$，其第 $k$ 阶差分为常数 $k!$。 已知 $R(x)$ 前 $k$ 项及对应的 $k$ 阶差分，即可推出所有项，找到 $R(x)=0$ 的根后即可直接还原。 这是这道题的超级加强版： [Problem - J - Codeforces](https://codeforces.com/gym/106626/problem/J) 最后修改：2026 年 09 月 08 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏