正睿二十连测
B
给定 \(n \times n\) 的矩阵 \(A\) ，长度为 \(m\) 的数组 \(b\) 以及 \(X, Y\)，问有多少个长度为 \(n\) 的数组 \(a\) 满足 \(A_{i, j} = a_i \oplus a_j \oplus X\) 或 \(a_i \oplus X \oplus Y\) 且 \(a\) 加入 \(m - n\) 个数后重排可以得到 \(b\)。
\(n \le m \le 2000, X, Y, b_i, A_{i, j} \le 2^{12} - 1\)。
首先先来判一下没有的情况。有几个条件。
-
\(A_{i, i} = X / Y\)。（\(/\) 表示或）
-
\(A_{i, j} = a_{i} \oplus a_j \oplus (X / Y)\)，\(A_{j, i}\) 同理。所以 \(A_{i, j} \oplus A_{j, i} = (0 / X \oplus Y)\)。
-
\(A_{1, i} = a_1 \oplus a_i \oplus (X / Y), A_{1, j} = a_1 \oplus a_j \oplus (X / Y)\)，得到 \(A_{1, i} \oplus A_{1, j} = a_i \oplus a_j \oplus (0 / X \oplus Y)\)。又有 \(A_{i, j} = a_i \oplus a_j \oplus (X / Y)\)，所以 \(A_{i, j} = A_{1, i} \oplus A_{1, j} \oplus (X / Y)\)。
判完无解了。实际上可以发现这样下来只有 \(n - 1\) 个方程了，\(a_{i} = a_{1} \oplus A_{i, j} \oplus (X / Y)\)。
于是枚举 \(a_1\)，那么 \(a_i\) 一定是在某对 \((x_i, y_i)\) 之间选择，然后就懵逼了，写了个 \(2^n\) 得到了 \(45pts\)。
经过题解的提示，实际上 \((x_i, y_i)\) 是不相交的，即不可能同时存在 \((x_i, y_i)\) 和 \((x_i, k)(k \ne y_i)\)，因为 \(x \oplus y\) 其实就是 \(X \oplus Y\)。
然后就好办了，令 \(c_i\) 表示 \(b\) 中 \(i\) 的个数，\(cnt_{x, y}\) 为 \((x, y)\) 出现的次数。那么答案就是 \(\prod\limits_{(x, y)} \sum\limits_{j = \max(0, cnt_{x, y} - c_y)}^{c_x} \binom{cnt_{x, y}}{j}\)。
直接做就是 \(O(m^2)\) 的。
赛时没想的那么清楚，是对于 \((i, j)\) 枚举了 \(a_{i, j}, a_{j, i}\) 怎么来的，判了后用 vector 存起来，所以没有发现 \(x \oplus y = X \oplus Y\) 这个重要性质。如果没有这个性质，似乎是只能暴搜做的。
当想不出来时，还是要多挖挖性质，想清楚每一步，化简出来说不定有新的发现。