当前位置: 首页 > news >正文

lzr 的区间(interval)

题目大意

题目传送门

给定一个序列 \(a\),问有多少个区间的异或和的二进制表示下一的个数为奇数。

思路

定义 \(f(l, r)\) 为区间 \([l, r]\) 之间的异或和,\(g(a)\) 表示 \(a\) 在二进制表示下 \(1\) 的个数。

因为 \(a \oplus a = 0\),所以可以利用类似前缀和的数组 \(s_i\) 表示前 \(i\) 个数的异或和。则 \(f(l, r)\) 就等于 \(s_r \oplus s_{l - 1}\)

所以问题转换为有多少个 \(l\)\(r\),使 \(g(s_r \oplus s_{l - 1}) \equiv 1 \ (mod \ 2)\) 为奇数,为了使式子更加简洁,不妨猜想 \(g(a \oplus b) \equiv (g(a) + g(b)) \ ( mod \ 2)\)

可以知道,\(a\)\(b\) 的二进制下如果在同一位最多出现一个 \(1\),那么是没有问题的。如果当第 \(i\)\(a\)\(b\) 都是 \(1\)\(1 + 1 - (1 \oplus 1) = 0\),所以 \(g(a \oplus b) = g(a) + g(b) - 2 * g(a \& b)\),因为 \(2\) 整除 \(2 * g(a \& b)\),所以\(g(a \oplus b) \equiv (g(a) + g(b)) \ ( mod \ 2)\)

所以问题进一步转化为求有多少组 \(l\)\(r\),使 \(g(l) + g(r) \equiv1 \ ( mod \ 2)\)

所以要么 \(g(l) \equiv1 \ ( mod \ 2)\),要么 \(g(r) \equiv1 \ ( mod \ 2)\),所以,求出有多少个 \(s_i \equiv1 \ ( mod \ 2)\),根据乘法原理就可以得出答案为 \(cnt_0 * cnt_1\),要注意,当 \(i = 0\) 时的 \(s[i]\) 也要统计!!!

代码

#include <iostream>
using namespace std;const int N = 300010;
long long n, s, a, cnt;int main() {freopen("interval.in", "r", stdin);freopen("interval.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++) {cin >> a;s ^= a;if (__builtin_popcountll(s) % 2) cnt++;}cout << cnt * (n - cnt + 1) << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=27639

相关文章:

  • IRB-120机械臂socket通信接受上位机指令运行程序段
  • 1.1.1.1 金融市场的定义与功能
  • 使用c#操作elasticsearch8
  • CF45C Dancing Lessons 题解
  • APUE学习笔记之文件IO(三) - Invinc
  • note
  • 供应链优化技术助力应对疫情挑战
  • 搜索关键词 - 呓语
  • 阅读《构建之法》产生的问题
  • 每日反思
  • 每日反思(2025.10.09)
  • 软件工程学习日志2025.10.9
  • 骄傲 雨伞边缘处的暗槽 从最原初裂缝开凿 被碰触和温暖击倒 停止思考
  • 1.1.1.2 直接融资vs间接融资的区别
  • 柳高国庆小小说创作比赛的构思和成文(未完成)
  • 骄傲 孔雀羽翎上的暗槽 从最肮脏裂缝开凿 被爱意和现实击倒 停止创造
  • 10.9 CSP-S模拟28 改题记录
  • 所以相信我初登场 不会让任何人失望 无论地位不管成败 全都逃不出神的覆掌
  • 被彼此笼罩 任歌声将我们缠绕 立下誓言后再自嘲 重复仲夏夜的舞蹈 吞下这毒药
  • 朝圣显像 不及那人将门扉轻轻叩响 欢迎来到我的城市 嗅玫瑰绽放
  • Git克隆项目运行指南
  • webpack library - 指南
  • 2025.10.9 月考游寄 - Amy
  • 被彼此笼罩 任回忆将我们缠绕 狂欢者戴上了镣铐 得益者撕裂了嘴角 吞下这毒药
  • QGIS导出TIF栅格图层
  • 七层协议
  • 20251009
  • 单调栈
  • 各种B站客户端
  • 10.9正式恢复