Educational Codeforces Round 155 (Rated for Div. 2) - D Sum of XOR Functions

学到的几个知识点:
1.拆位
对于整体上的异或操作可以转化为31个二进制位上的操作,每一位再×上 。
将一次操作拆为31次来方便操作。
2.
s[i]表示异或前缀和,l~r间的异或和为s[r] ^ s[l - 1] ---->
拆完位后这个公式还能再推出一个性质:
只有s[r] != s[l - 1]时这段区间的异或和才为1,来以右端点为1还是0来讨论一下:
对于每一位1,只有左端点的左边一位为0时才有值,才可以计算进去
对于每一位0,只有左端点的左边一位为1时才有值,才可以计算进去
对于一位上的1,设当前为r,左边的为0的点为l,那要承的数就是(r - l),
如果这样的l有k个,就是k * r - ()
这样就算出来了对于每一个数的每一位的贡献 时间复杂度 O(31 * n)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;const int N = 300010, mod = 998244353;int n;
int a[N];
ll f[40][2], cnt[40][2];int main()
{IOScin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];a[i] ^= a[i - 1];//cout << a[i] << ' ';}//cout << endl;ll ans = 0;for(int i = 0; i <= n; i ++){for(int j = 0; j <= 30; j ++){if(a[i] >> j & 1){ans += (1ll << j) % mod * (((cnt[j][0] * i - f[j][0]) % mod + mod) % mod);ans %= mod;f[j][1] = (f[j][1] + i) % mod;cnt[j][1] ++;}else{ans += (1ll << j) % mod * (((cnt[j][1] * i - f[j][1]) % mod + mod) % mod);ans %= mod;f[j][0] = (f[j][0] + i) % mod;cnt[j][0] ++;}}}cout << ans;return 0;
}
相关文章:
Educational Codeforces Round 155 (Rated for Div. 2) - D Sum of XOR Functions
学到的几个知识点: 1.拆位 对于整体上的异或操作可以转化为31个二进制位上的操作,每一位再上 。 将一次操作拆为31次来方便操作。 2. s[i]表示异或前缀和,l~r间的异或和为s[r] ^ s[l - 1] ----> 拆完位后这个公式还能再推出一个性…...
[C++ 网络协议] I/O流分离所带来的半关闭问题
1.问题和解决方法 根据所学内容,I/O流分离现如今有如下2种方法: 1.调用进程fork函数,分离出子进程,主进程和子进程分别进行输入流的读和输出流的写。 2.用FILE指针按读模式和写模式将输入流和输出流进行区分。 第一种方法&#…...
根据文章段落内容自动插入图片php版
每篇内容根据段落判断插入图片代码附上: $chatd"<table>";if(stripos($content,$chatd)0){//随机输出三张图功能if($moduleid!37 &&$thumb){//判断是否存在图$idrand(1,999999);$midrand(1,9999999);$getimg"http://www.nongpin88.co…...
在GEHC的第一个sprint记录
今天是进入GEHC XR ATX的第25天,是周日,下周二我的第一个sprint也就到期了,幸好在这周五晚上完成了,当然还差个分享。在此记录第一个sprint中两个story过程。 第一个story是操作固定式DR设备进行exposure整个过程。这是所有新人必…...
MFC 绘图
效果图:三张bmp图 字 竖线 组成 在OnPaint()函数中 CPaintDC dc(this);CRect rect;GetClientRect(&rect); //获取客户区矩形CDC dcBmp; //定义并创建一个内存设备环境dcBmp.CreateCompatibleDC(&dc); //创建兼容性DCCBitmap …...
算法 用两个栈实现队列-(栈+队列)
牛客网: BM42 题目: 用两个栈模拟队列 思路: stack1, stack2两个栈,入队只选择stack1, 出队只选择stack2, 如果stack2为空,将stack1元素全部出栈并入栈stack2。 代码: // gopackage mainvar stack1 [] int var stack2 [] intfunc Push(node int) {st…...
Android单编模块报FAILED: ninja: unknown target ‘MODULES-IN-vendor错误解决
有时我们需要单编Android AOSP一个APK或库文件或二进制,用来调试。 但可能这个模块本身是不参与系统整编编译的。我们在使用mmm或mm单独编译时就会报这个错误。 在检查Android.mk或Android.bp无误后,就要怀疑是不是这个目录的上级目录是不是没有包含这…...
地球的某一片红薯地中秋圆《乡村振兴战略下传统村落文化旅游设计》——旅行季许少辉八月新书辉少许想象和世界一样宽广
地球的某一片红薯地中秋圆《乡村振兴战略下传统村落文化旅游设计》——旅行季许少辉八月新书辉少许想象和世界一样宽广 地球的某一片红薯地中秋圆《乡村振兴战略下传统村落文化旅游设计》——旅行季许少辉八月新书辉少许想象和世界一样宽广]...
Zookeeper-命令操作
命令操作 命令操作1) Zookeeper 数据模型2) Zookeeper 服务端常用命令3) Zookeeper 客户端常用命令 命令操作 1) Zookeeper 数据模型 ZooKeeper 是一个树形目录服务,其数据模型和Unix的文件系统目录树很类似,拥有一个层次化结构。 这里面的每一个节点都被称为&am…...
eclipse 添加注释
在 Eclipse 中,你可以使用注释来为你的代码添加说明、文档或标记。以下是如何在 Eclipse 中添加注释的一些方法: 单行注释:你可以使用单行注释来注释一行代码。在要注释的代码行前面添加双斜杠 // 即可。例如: // 这是一个单行注…...
Linux网络编程- 网络字节顺序
基本概念 网络字节顺序是一种规定的数据表示格式,被用于TCP/IP协议栈,特别是在网络传输数据时。它确保不同的计算机和架构之间可以无缝地通信。网络字节顺序是大端字节序(big-endian)。 字节序的背景 计算机存储多字节数据&…...
如何永久关闭WPS任务窗口?
1、按住任务窗口上的浮动按钮,将其拖出来成悬浮窗口。 第二步,使用火绒弹窗拦截,选中弹出的窗口,进行拦截。注意:拦截次数为2次。即进行2次操作。 操作两次后,弹窗被拦截,此时Word文档改为双页显…...
Cesium 问题:加载 geojson 数据量大浏览器会崩,使用primitive方式加载
文章目录 问题分析 问题 之前加载geojson数据都是使用dataSource和entity的方式,但是当数据量大时,浏览器就会崩掉:提示浏览器内存不足,已暂停渲染 分析 使用primitive方式加载数据,可以提高加载渲染效率。实现方法…...
C++ Primer----1.5类简介 章节练习
头文件 Sales_item.h #ifndef SALESITEM_H #define SALESITEM_H #include <iostream> #include <string>class Sales_item{ public:Sales_item(const std::string &book):isbn(book),units_sold(0),revenue(0.0){}Sales_item(std::istream &is){ is >&…...
爬楼梯Java(斐波那契数列)
题目:有n阶楼梯,一次只能爬一层或者两层,请问有多少种方法? 这类题目其实都可以用斐波那契数列来解决,比如: 一阶楼梯只有一种方法 二阶楼梯有(11,2)两种方法 三阶楼梯有(111,12,21)三种方法 四阶楼梯有(1111,121,112,22,211)五种方式 五阶楼梯有(11111,1112,122,1211,1…...
Maven项目package为jar包后在window运行报A JNI error has occurred
原因:本地java版本与项目结构中使用的java版本不一致(之前因为别的需求把idea的java版本改为了18) 解决方法 打开项目结构,将idea的java版本改为与本地一致 再修改项目中的pom.xml 重新编译,package即可...
iview 的table表格组件使单元格可编辑和输入
表格的列定义中,在需要编辑的字段下使用render函数 template表格组件 <Table border :data"data" :columns"tableColumns" :loading"loading"></Table>data中定义table对象 table: {tableColumns: [{title: 商品序号,k…...
统计的基本概念及抽样分布
文章目录 🍋引言🍋总体(Population)🍋总体参数 🍋样本(Sample)🍋随机样本🍋样本统计量 🍋统计量(Statistic)🍋…...
【C++】class的设计与使用(四)this指针
this指针 this作用域是在类内部,只能在成员函数中使用;this在成员函数的开始前构造,在成员函数的结束后清除;编译器在编译的时候也会自动加上this,它作为非静态成员函数的隐含形参,对各成员的访问均通过th…...
mysql 导入sql文件
mysql 导入sql文件 sudo mysql -uroot -p123456 -h127.0.0.1 sudo mysql -uroot -p123456 -h127.0.0.1然后 show databases;然后 use 数据库名称; 然后 source 20230920031001.sql;如果不加 -h127.0.0.1 可能会出现错误 /var/lib/mysql.sock error 通过 navicat导入的话&am…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
