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…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
