NOIP2023模拟13联测34 A. origenNOIP2023模拟13联测34 A. origen
NOIP2023模拟13联测34 A. origen
文章目录
- NOIP2023模拟13联测34 A. origen
- 题目大意
- 思路
- code
题目大意
给定 n n n 个整数 a 1 , a 2 , a 3 ⋯ a n a_1,a_2,a_3\cdots a_n a1,a2,a3⋯an ,求
∑ i = 1 n ∑ j = i n ( ⊕ k = i j a k ) 2 m o d 998244353 \sum_{i = 1}^n\sum_{j = i}^n(\oplus_{k = i}^ja_k)^2 \mod 998244353 i=1∑nj=i∑n(⊕k=ijak)2mod998244353
n ≤ 2 ∗ 1 0 5 , 0 ≤ a i ≤ 2 ∗ 1 0 5 n\le 2 * 10^5 , 0\le a_i \le 2 * 10 ^5 n≤2∗105,0≤ai≤2∗105
思路
设 s i = ⊕ j = 1 i a j s_i = \oplus_{j = 1}^i a_j si=⊕j=1iaj ,则原式变为:
∑ i = 0 n − 1 ∑ j = 1 n ( s i ⊕ s j ) 2 \sum_{i = 0}^{n - 1} \sum_{j = 1}^n (s_i \oplus s_j)^2 i=0∑n−1j=1∑n(si⊕sj)2
按位考虑,一个数可以用二次幂的和来表示。考虑怎么处理平方。
因为:
( ∑ i = 1 n a i ) 2 = ∑ i = 1 i a i 2 + 2 ∑ i = 1 n − 1 ∑ j = i + 1 n a i ∗ a j (\sum_{i = 1}^n a_i)^2 = \sum_{i = 1}^i a_i^2+ 2\sum_{i = 1}^{n - 1}\sum_{j = i +1}^n a_i*a_j (i=1∑nai)2=i=1∑iai2+2i=1∑n−1j=i+1∑nai∗aj
把两部分分开处理。
先处理前面的那项
把 i i i 的每一位分开求贡献,当前处理到第 j j j 位
设前 i − 1 i - 1 i−1 个数这一位为 0 0 0 的数有 s 0 s0 s0 个,为 1 1 1 的数有 s 1 s1 s1 个
那么求这一位的贡献
- 若当前这一位为 1 1 1 : 2 j ∗ 2 ∗ s 0 2^j*2*s0 2j∗2∗s0
- 若当前这一位为 0 0 0 : 2 j ∗ 2 ∗ s 1 2^j*2*s1 2j∗2∗s1
然后处理后面的那项
先枚举两位 j 1 , j 2 j1 , j2 j1,j2
当前处理到第 i i i 位
设 s u m k , l sum_{k , l} sumk,l 为前面 i − 1 i - 1 i−1 个数的第 j 1 j1 j1 位为 k k k ,第 j 2 j2 j2 位为 l l l 的个数
设第 i i i 个数这两位分别是 x , y x , y x,y
那么这里的贡献为: 2 ∗ 2 j 1 ∗ 2 j 2 ∗ s u m ! x , ! y 2 *2^{j1} * 2^{j2} *sum_{!x , !y} 2∗2j1∗2j2∗sum!x,!y
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int mod = 998244353 , inf = 2e5;
int n , a[inf + 5] , s[inf + 5] , sum[2][2];
long long ans;
int main () {freopen ("origen.in" , "r" , stdin);freopen ("origen.out" , "w" , stdout);scanf ("%d" , &n);fu (i , 1 , n) scanf ("%d" , &a[i]) , s[i] = s[i - 1] ^ a[i];for (int j = 1 , l = 1 ; l <= inf ; l <<= 1 , j ++) {for (int i = 1 , s0 = 1 , s1 = 0 ; i <= n ; i ++) {if ((1 << (j - 1)) & s[i]) ans = (ans + 1ll * l * l * s0 % mod) % mod , s1 ++;else ans = (ans + 1ll * l * l * s1 % mod) % mod , s0 ++;}}bool x , y;for (int j1 = 1 , l1 = 1 ; l1 <= inf ; l1 <<= 1 , j1 ++) {for (int j2 = j1 + 1 , l2 = l1 << 1 ; l2 <= inf ; l2 <<= 1 , j2 ++) {sum[0][0] = 1 , sum[0][1] = sum[1][0] = sum[1][1] = 0;fu (i , 1 , n) {x = s[i] & (1 << (j1 - 1)) , y = s[i] & (1 << (j2 - 1));ans = (ans + 2ll * l1 * l2 * sum[!x][!y] % mod) % mod;sum[x][y] ++;}}}printf ("%lld" , ans);return 0;
}
相关文章:
NOIP2023模拟13联测34 A. origenNOIP2023模拟13联测34 A. origen
NOIP2023模拟13联测34 A. origen 文章目录 NOIP2023模拟13联测34 A. origen题目大意思路code 题目大意 给定 n n n 个整数 a 1 , a 2 , a 3 ⋯ a n a_1,a_2,a_3\cdots a_n a1,a2,a3⋯an ,求 ∑ i 1 n ∑ j i n ( ⊕ k i j a k ) 2 m o d 998244353 \…...
HttpClient学习(Java)
一、介绍 HttpClient 是Apache Jakarta Common 下的子项目,可以用来提供高效的、最新的、功能丰富的支持 HTTP 协议的客户端编程工具包,并且它支持 HTTP 协议最新的版本和建议。 我们可以通过这个HttpClient工具,在java代码中去构造和发送ht…...
信息系统项目管理师之各工具的定义及解释
数据收集技术 用于从各种渠道收集数据与信息。 数据分析技术 用于组织评估和评价数据与信息。 数据表现技术 用于显示用来传递数据和信息的图形方式或其他方法。 决策技术 用于从不同备选方案选择行动方案。 沟通技巧 用于在干系人之间传递信息。 人际关系与团队技能…...
golang的defer执行时机案例分析
package main import "fmt"func calcFunc(x int, y int) int {return x y }func main() {// defer语句的执行顺序是,从右到左,逆序执行deferDemo()// deferDemo1函数demo1 : deferDemo1()fmt.Println(demo1) // 0// deferDemo2函数demo2 : deferDemo2()f…...
2.HTML中常用浏览器
2.常用浏览器 2.1 什么是浏览器 浏览器是网页显示,运行的平台。常用的浏览器有IE,火狐,谷歌,Safari和Opera等 平时成为五大浏览器 2.2 浏览器内核 浏览器内核(渲染引擎):负责读取网页内容&…...
Vue 监听store数据变化
天冷了,手也冷了,于学问于个人成长不能因为冷而荒废。毕业这么多年,只能感慨。这样努力的工作只是解决了温保问题,何时才能任性的过一回说走就走的自由生活? 大抵这样的梦想也就只能停留在梦里与期待中吧,与…...
智能交通和自动驾驶技术
一、定义 智能交通和自动驾驶技术是指利用先进的信息技术和人工智能技术,实现交通系统的智能化和自动化。智能交通和自动驾驶技术不仅可以提高交通系统的效率和安全性,还可以改善人们的出行体验,促进城市可持续发展。 智能交通和自动驾驶技…...
CentOS7安装部署StarRocks
文章目录 CentOS7安装部署StarRocks一、前言1.简介2.环境 二、正文1.StarRocks基础1)架构图2)通讯端口 2.部署服务器3.安装基础环境1)安装JDK 112)修改机器名3)安装GCC4)关闭交换分区(swap&…...
树形Dp 2925. 在树上执行操作以后得到的最大分数
2925. 在树上执行操作以后得到的最大分数 两次DFS class Solution { public:// 节点状态有两种,选和不选,// dp(u, fa, 0) 不选u 节点,其他节点都可以选,值为以u为根的子树的所有节点的和- 根节点的值。// dp(u, fa, 1) 选u节点&…...
选择企业云盘?品牌推荐和评价解析
企业云盘是如今热门的企业协作工具,为企业提供了文件存储、文件共享服务。市面上的企业云盘千千万,到底哪个企业云盘好用?哪些品牌值得信赖呢? 好用的企业云盘,不能不提,Zoho Workdrive企业云盘为企业提供…...
redis: 记录一次线上redis内存占用过大问题解决过程
引言 记录一次线上redis占用过大的排查过程,供后续参考 问题背景 测试同事突然反馈测试环境的web系统无法登陆,同时发现其他子系统也存在各类使用问题 排查过程 1、因为首先反馈的是测试环境系统无法登陆,于是首先去查看了登陆功能的报错…...
数据资产、数字资产、数据资源及数据资产入表
数据要素 《中共中央关于坚持和完善中国特色社会主义制度推进国家治理体系和治理能力现代化若干重大的决议》(2019) 首次将数据列为生产要素 《关于构建更加完善的要素市场化配置体制机制的意见》(2020.3) 数据成为土地、劳动力、…...
Docker之Centos安装
介绍 Docker官方建议在Ubuntu中安装,因为Docker是基于Ubuntu发布的, 而且一般Docker出现的问题Ubuntu是最先更新或者打补丁的。 在很多版本的CentOS中是不支持更新最新的一些补丁包的。由于我们学习的环境都使用的是CentOS,因此这里我们将Do…...
SQL注入漏洞:CMS布尔盲注python脚本编写
SQL注入漏洞:CMS布尔盲注python脚本编写 文章目录 SQL注入漏洞:CMS布尔盲注python脚本编写库名爆破爆破表名用户名密码爆破 库名爆破 import requests #库名 database"" x0 while requests.get(urlf"http://10.9.47.77/cms/show.php?id33%20and%20length(data…...
security
Java Security 是一个用于在 Java 平台上提供安全性的框架。下面是 Java Security 的一些主要知识点: 1. 加密和解密:Java Security 提供了一组加密和解密 API,可以实现各种加密标准,如 AES、DES、RSA 等。 2. 数字签名…...
了解web3,什么是web3
Web3是指下一代互联网,它基于区块链技术,将各种在线活动更加安全、透明和去中心化。Web3是一个广义的概念,它包括了很多方面,如数字货币、去中心化应用、智能合约等等。听不懂且大多数人听到这个东西,直觉感觉就像骗子…...
Harbor企业级Registry基础镜像仓库的详细安装使用教程(保姆级)
Harbor Docker 官方提供的私有仓库 registry,用起来虽然简单 ,但在管理的功能上存在不足。 Harbor是vmware一个用于存储和分发Docker镜像的企业级Registry服务器,harbor使用的是官方的docker registry(v2命名是distribution)服务去完成。 ha…...
Linux系统下数据同步服务RSYNC
一、RSYNC概述 1、什么是rsync rsync的好姐妹 sync 同步:刷新文件系统缓存,强制将修改过的数据块写入磁盘,并且更新超级块。 async 异步:将数据先放到缓冲区,再周期性(一般是30s)的去同步到磁…...
Docker介绍及其常用命令
Docker是一种容器化技术,可以打包应用程序及其依赖项,并将其作为独立的进程运行。它实现了操作系统级别的虚拟化,允许不同容器之间相互隔离,同时提高了应用程序的可移植性和安全性。Docker可以快速部署和扩展应用程序,…...
SwissArmyTransformer瑞士军刀工具箱使用手册
Introduction sat(SwissArmyTransformer)是一个灵活而强大的库,用于开发您自己的Transformer变体。 sat是以“瑞士军刀”命名的,这意味着所有型号(例如BERT、GPT、T5、GLM、CogView、ViT…)共享相同的backo…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
智能职业发展系统:AI驱动的职业规划平台技术解析
智能职业发展系统:AI驱动的职业规划平台技术解析 引言:数字时代的职业革命 在当今瞬息万变的就业市场中,传统的职业规划方法已无法满足个人和企业的需求。据统计,全球每年有超过2亿人面临职业转型困境,而企业也因此遭…...
leetcode73-矩阵置零
leetcode 73 思路 记录 0 元素的位置:遍历整个矩阵,找出所有值为 0 的元素,并将它们的坐标记录在数组zeroPosition中置零操作:遍历记录的所有 0 元素位置,将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...
DeepSeek越强,Kimi越慌?
被DeepSeek吊打的Kimi,还有多少人在用? 去年,月之暗面创始人杨植麟别提有多风光了。90后清华学霸,国产大模型六小虎之一,手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水,单月光是投流就花费2个亿。 疯…...
Linux基础开发工具——vim工具
文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...
