非常好的容斥题目。上锁巡游可以有剧情互动嘛。我想看你们谈恋爱。P11651 [COCI 2024/2025 #4] Xor - 洛谷 (luogu.com.cn)1.基础版考场做法。看到异或想到拆位。对于每一个二进制位统计有多少个数对这一位为 1如果是奇数对则该位在最终答案为 1。设二进制第 0 位是最低位。首先我们只取所有数二进制第位及以下的位防止大数干扰结果。数对和二进制第位为 1的情况1两个数第位都为 0位以下的进位到2只有一个数第位为 1位以下不进位3两个数第位都为 1位以下的进位到如果转换成区间那么俩数和在的第位为 1。但如果在里则第位为 0大于等于则第位为 1。这是一个小小容斥我们可以 大于等于 大于等于- 大于等于的。至于怎么求大于等于某个数的数对个数先排序再双指针就可以了。注意指针的遗留位置时间复杂度为。最大是极限能在洛谷上过。#includebits/stdc.h using namespace std; typedef long long LL; const int N 5e5 10; LL a[N], aa[N]; int n; LL get_(LL x) { int j n; LL res 0; aa[0] 0; for (int i 1; i n; i ) { j max(j, i); while (aa[i] aa[j] x j i) { j --; } res res n - j; } return res; } int main () { ios::sync_with_stdio(false); cin.tie(0); cin n; for (int i 1; i n; i ) { cin a[i]; } LL ans 0; for (int i 0; i 30; i ) { LL t (1ll (i 1)) - 1; for (int j 1; j n; j ) { aa[j] a[j] t; } sort (aa 1, aa n 1); LL sum1 get_(1ll i); LL sum2 get_(1ll (i 1)); LL sum3 get_((1ll i) (1ll (i 1))); LL sum sum1 sum3 - sum2; if (sum 1) { ans (1ll i); } } cout ans \n; return 0; }2.进阶版排序还是太费时间了如果我们能优化掉这部分时间就很健康。刚好是从小到大枚举二进制位排序可以用类似基数排序的方式分层排序。时间复杂度。请看注释#includebits/stdc.h using namespace std; typedef long long LL; const int N 5e5 10; LL a[N], aa[N], b[N], c[N], d[N]; int n; LL get_(LL x) { int j n; LL res 0; aa[0] 0; for (int i 1; i n; i ) { j max(j, i); while (aa[i] aa[j] x j i) { j --; } res res n - j; } return res; } int main () { ios::sync_with_stdio(false); cin.tie(0); cin n; for (int i 1; i n; i ) { cin a[i]; } LL ans 0; for (int i 0; i 30; i ) { LL t (1ll (i 1)) - 1; int bl 0, cl 0; for (int j 1; j n; j ) { // 根据 a_i 的第 i 位是否为 1 分组 // 为 1 的肯定不为 0 的大统一排到后面去 if (a[j] (1ll i)) { // 如果 a_i 的第 i 位为 1 cl ; c[cl] j; } else { // 如果 a_i 的第 i 位为 0 bl ; b[bl] j; } } // 注意这里 b 和 c 数组存的都是 a 的下标 // 基数排序是稳定的如果两个数的第 i 位相同 // 并不会改变它们的相对位置即按照上一轮排序的相对位置 // 而上一轮就是根据前 i - 1 位的大小 for (int j 1; j bl; j ) { d[j] a[b[j]]; // 选已经分好的下标 } for (int j 1; j cl; j ) { d[bl j] a[c[j]]; } for (int j 1; j n; j ) { a[j] d[j]; // 复制回 a 数组 } for (int j 1; j n; j ) { aa[j] a[j] t; // 取前 i 位 } LL sum1 get_(1ll i); LL sum2 get_(1ll (i 1)); LL sum3 get_((1ll i) (1ll (i 1))); LL sum sum1 sum3 - sum2; if (sum 1) { ans (1ll i); } } cout ans \n; return 0; }3.代码短短版真的很短只是我的码风长以下就没有时间复杂度的优化了单纯就是代码短。如果我们还是取所有数二进制第位及以下的位但只分为两种情况数对和二进制第位为 1 的情况不考虑a至少一个数第位为 1要求b位以下的进位到要求对于这两种情况的相加集合我们一种种情况分析对于强制下标的的情况分析1两个数第位都为 0不进位到——不会被计算2两个数第位都为 0进位到仅在进位 ——会被计算 1 遍3只有一个数第位为 1不进位到如果的第位为 1 ——会被计算 1 遍如果的第位为 1 ——会被计算 1 遍——在确定的一对中仅会被计算 1 遍4只有一个数第位为 1进位到如果的第位为 1 ——会被计算 2 遍如果的第位为 1 ——会被计算 2 遍——在确定的一对中仅会被计算 2 遍在3和4中因为只有一个数第位为 1可以保证a只会累积 1 次而只要进位一定会被统计 1 次5两个数第位都为 1不进位到——会被计算 2 遍6两个数第位都为 1进位到——会被计算 3 遍在5和6中因为两个数第位都为 1可以保证a会被计算 2 次而只要进位就会被统计 1 次在以上分类讨论中我们可以发现只有三种情况会被计算偶数遍1两个数第位都为 0不进位到4只有一个数第位为 1进位到5两个数第位都为 1不进位到这三种情况都是我们不想计算到的在累积奇偶性答案中计算偶数遍可以当作没累积。就此我们有了最优解代码时间复杂度仍是。同样可以使用基数排序优化代码更短。对了还有的情况直接线性单独异或。肯定有人问为什么之前不能把的情况一起考虑进去呢因为当两个数第位都为 1a却只会累积 1 次不能和其他情况一同考虑。#includebits/stdc.h using namespace std; typedef long long LL; const int N 5e5 10; LL a[N], aa[N], b[N]; int n; LL get_(LL x) { int j n; LL res 0; aa[0] 0; for (int i 1; i n; i ) { j max(j, i); while (aa[i] aa[j] x j i) { // 这里要改下保证 j ! i - 1 // 即对应下标不会取到 i j --; } res res n - j; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n; for (int i 1; i n; i ) { cin a[i]; } LL ans 0; for (int i 0; i 30; i ) { LL t (1 i) - 1, sum 0; for (int j 1; j n; j ) { aa[j] a[j] t; } sum get_(1ll i); int bl 0; for (int j 1; j n; j ) { if (a[j] (1ll i)) { sum (n - 1); } else { bl ; b[bl] a[j]; } } if (sum 1) { ans (1ll i); } for (int j 1; j n; j ) { if (a[j] (1ll i)) { bl ; b[bl] a[j]; } } memcpy(a, b, sizeof(a)); } for (int i 1; i n; i ) { ans ans ^ (a[i] a[i]); } cout ans \n; return 0; }