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…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...
C++ 类基础:封装、继承、多态与多线程模板实现
前言 C 是一门强大的面向对象编程语言,而类(Class)作为其核心特性之一,是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性,包括封装、继承和多态,同时讨论类中的权限控制,并展示如何使用类…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
