Two Missing Numbers
Source
Statement
通信题。有一个长度为 \(n\) 的序列 \(a\ (0\le a_i<2^{64})\)，满足其中恰好两种数出现次数为 \(1\)，其余数字出现次数为 \(2\)。该序列被任意分成两半，分两次喂给你的程序。第一次运行你会得到序列的前半段，你需要输出两个 \(\mathtt{uint64}\)；第二次运行你会得到序列的后半段以及第一次输出的两个整数，你需要输出两个 \(\mathtt{uint64}\) 表示那两个出现次数为 \(1\) 的数。
Solution
首先把已经出现 \(2\) 次的数字扔了。现在相当于分两次获得集合 \(S,T\)，需要找到 \(S\oplus T\)，记这个结果为 \(\{x,y\}\)。
考虑神秘哈希，记 \(P=18446744073709551557\)，即 \([0,2^{64})\) 中的最大质数。考虑建立一个简单的单射 \(f:[0,2^{64})\cap a\to[0,P)\cap\mathbb{Z}\)。一个简单的想法是 \(f(x)=x\operatorname{xor} M\)，其中 \(M\) 是一个自己脸滚键盘得到的常数。因为 \(2^{64}-P=59\)，所以可以认为 \(f(a_i)\ge P\) 的概率很小（如果非常不幸出现了，可以再滚一个 \(M\) 提交）。
第一次运行，我们计算 \(\displaystyle a_1=\sum_{x\in S}f(x)\bmod P,\ b_1=\prod_{x\in S}f(x)\bmod P\)，第二次运行类似地计算 \(a_2,b_2\)。接下来，依次尝试一下几种情形：
-
\(x\in T\land y\in T\)：
可以得到：
\[\begin{cases} f(x)+f(y)\equiv a_2-a_1\pmod P \\ f(x)\cdot f(y)\equiv b_2/b_1\pmod P \end{cases} \]直接韦达定理解二次方程（需要 Cipolla 开根）。然后映射回去，验证答案。
-
\(x\in T\land y\in S\)：
可以得到：
\[\begin{cases} f(x)-f(y)\equiv a_2-a_1\pmod P \\ f(x)/f(y)\equiv a_2/a_1\pmod P \end{cases} \]是一个一次方程，直接解。然后映射回去，验证答案。
-
\(x\in S\land y\in S\)：
可以得到：
\[\begin{cases} f(x)+f(y)\equiv a_1-a_2\pmod P \\ f(x)\cdot f(y)\equiv b_1/b_2\pmod P \end{cases} \]也是二次方程，直接解。然后映射回去，验证不了，不验证了。
由题目限制可知至少解出一个解。为什么要按照上面的顺序依次尝试呢？因为解这个方程时只知道 \(T\)，所以按照验证难度从易到难尝试错误率更小。
Sets May Be Good
Source
Statement
给定 \(n\ (n\le 1000)\) 个点无向图 \(G=(V,E)\)。求导出子图边数为偶数的点集数量。
Solution
考虑一个 \(n\) 元二次多项式 \(\displaystyle F(x_1,\dots,x_n):=\sum_{i\neq j,\ (i,j)\in E}x_ix_j+\sum_{(i,i)\in E}x_i\)。题目相当于求 \(n\) 元组 \((x_1,\dots,x_n)\in \{0,1\}^n\) 使得 \(F(x_1,\dots,x_n)\bmod 2=0\)。
直接计算 \(=0\) 的方案有些困难，所以可以考虑计算 \(=0\) 和等于 \(=1\) 的方案数差值。
考虑拆开 \(F\)：\(F(x_1,\dots,x_2)=x_1L(x_2,\dots,x_n)+Q(x_2,\dots,x_n)\)。
如果 \(L(x_2,\dots,x_n)=1\)，那么对于每一种 \(x_2,\dots,x_n\) 方案，\(x_1\) 选与不选恰好对应两种最终 \(F\) 值不同的方案，所以对差值的共线为 \(0\)。
那么只剩下 \(L(x_2,\dots,x_n)=0\) 的情形。注意到 \(L(x_2,\dots,x_n)\) 是一个一次的多项式，所以可以移项得到 \(x_2\) 关于 \(x_3,\dots,x_n\) 的表达式。将这个表达式回带到 \(Q\) 得到 \(Q'(x_3,\dots,x_n)\)。那么我们就是要求 \(Q'(x_3,\dots,x_n)=k\ (k\in\{0,1\})\) 的方案数，这是一个形式相同子问题，递归计算即可。
时间复杂度 \(O(n)\)（吐槽数据范围）。
HoMaMaOvO 0:06 过了，天知道怎么做到的。
标签：dots,验证,pmod,sum,记录,cases,equiv From： https://www.cnblogs.com/ExplodingKonjac/p/17766348.html