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

2024牛客寒假算法基础集训营2-c Tokitsukaze and Min-Max XOR

来源

题目

Tokitsukaze 有一个长度为 n 的序列 a1,a2,…,an和一个整数 k。

她想知道有多少种序列 b1,b2,…,bm满足:
 


其中 ⊕\oplus⊕ 为按位异或,具体参见 百度百科:异或 

答案可能很大,请输出  mod1e9+7 后的结果。

输入描述:

第一行包含一个整数 T(1≤T≤2e5),表示 T 组测试数据。对于每组测试数据:第一行包含两个整数 n, k (1≤n≤2⋅e5; 0≤k≤1e9)。第二行包含 nnn 个整数 a1,a2,…,an (0≤ai≤1e9)。

输出描述:

对于每组测试数据,输出一个整数,表示答案   mod1e9+7  后的结果。

输入

3
3 2
1 3 2
5 3
1 3 5 2 4
5 0
0 0 0 0 0

输出

6
10
31

思路

       容易知道 b1,…,bm 实际上是 a 的一个子序列,并且由于我们只关注子序列中的最大值和最小值,因此可以先对 a 从小到大排序,再选择子序列。接着对子序列中的最大值进行分类,可以分成 n 类。即从左到右依次枚举 ai 作为子序列中的最大值,那么最小值就会在 aj, j∈[0,i] 中选。当满足 ai⊕aj≤k,那么以 ai 为最大值,aj 为最小值的子序列的数量就是 2的max{0,i−j−1}次方,特别的当 i=j 时答案为 1。

       暴力的做法就是逐个枚举 aj 判断是否满足条件,时间复杂度是 O(n^{2}) 的。由于涉及到异或运算所以尝试能不能用 trie 来维护 aj 的信息。如果 aj 满足条件,那么对答案的贡献是 2^{i-j-1},也就是 \frac{1}{2^{j+1}}*2^{i},因此在把 aj 按位插入 trie 中时,同时在对应节点加上\frac{1}{2^{j+1}}

       枚举到 ai 时,此时已经往 trie 中插入了 a0∼ai−1,枚举 ai 的每一位,用 xi 和 ki 分别表示 ai 和 k 在二进制下第 i 位上的值,s表示累加和。

        1.当xi=1,ki=1时,显然另一数aj这一位是1的情况都是可以的,因为 1⊕1=0<1,所以s加上这一位为1的节点的值了,下一步走0节点。

        2.当xi=0,ki=1时,同理s加上0节点的值,下一步走1节点.

        3.当xi=1,ki=0时,0节点必然不成立,因为 1⊕0=1>0,下一步走1节点。

        4.当xi=0,ki=0时,同理,1节点必然不成立,下一步走0节点。

最后以 ai 为最大值的子序列的数量就是s*2^{i}+1

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define double long double
typedef long long ll;
const int N = 2e5+100;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f3f3f3f;
//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int a[N];
int to[N * 35][2];
int val[N * 35];
int tot = 0;void insert(int x,int c) {int p = 0;for (int i = 30; i >= 0; i--) {int v = (x >> i & 1);if (!to[p][v]) {to[p][v] = ++tot;}val[to[p][v]] = (val[to[p][v]] + c) % mod;p = to[p][v];}
}int sum(int x,int k) {int p = 0, res = 0;for (int i = 30; i >= 0; i--) {int vx = (x >> i & 1), vk = (k >> i & 1);if (vk == 1 && vx == 1) {res = (res + val[to[p][1]]) % mod;p = to[p][0];} else if (vk == 1 && vx == 0) {res = (res + val[to[p][0]]) % mod;p = to[p][1];} else {p = to[p][vx];}if (!p) break;if (!i) res = (res + val[p]) % mod;}return res;
}int ksm(int x,int n) {int res = 1;while (n) {if (n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;
}void solve() {int n,k;cin >> n >> k;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);tot = 0;for (int i = 0; i <= n * 32; i++) {val[i] = 0;to[i][0] = to[i][1] = 0;}int ans = 0;for (int i = 1; i <= n; i++) {ans = (ans + 1 + ksm(2,i - 1) * sum(a[i - 1],k) % mod) % mod;insert(a[i - 1],ksm(ksm(2,i),mod - 2));}cout << ans << '\n';
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--)solve();return 0;
}

相关文章:

2024牛客寒假算法基础集训营2-c Tokitsukaze and Min-Max XOR

来源 题目 Tokitsukaze 有一个长度为 n 的序列 a1,a2,…,an和一个整数 k。 她想知道有多少种序列 b1,b2,…,bm满足&#xff1a; 其中 ⊕\oplus⊕ 为按位异或&#xff0c;具体参见 百度百科&#xff1a;异或 答案可能很大&#xff0c;请输出  mod1e97 后的结果。 输入描述…...

C语言:指针的基础详解

目录 1. 内存 2. 取地址& 3. 指针变量 4. 解引用 4.1 *解引用 4.2 []解引用 4.3 ->解引用 5. 指针变量的大小 5.1 结论 6. 指针运算 7. void* 指针 8. const修饰指针 8.1 const修饰变量 8.2 const修饰指针变量 8.3 结论 9. 野指针 9.1 为什么会出现野指…...

PHP+vue+mysql校园学生社团管理系统574cc

运行环境:phpstudy/wamp/xammp等 开发语言&#xff1a;php 后端框架&#xff1a;Thinkphp 前端框架&#xff1a;vue.js 服务器&#xff1a;apache 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat/phpmyadmin 前台功能&#xff1a; 首页&#xff1a;展示社团信息和活动…...

VS Code中主程序C文件引用了另一个.h头文件,编译时报错找不到函数

目录 一、问题描述二、问题原因三、解决方法四、扩展五、通过CMake进行配置 一、问题描述 VS Code中主程序C文件引用了另一个.h头文件&#xff0c;编译时报错找不到函数 主程序 main.c #include <stdio.h> #include "sumaa.h"int main(int, char**){printf(&q…...

边缘计算:重塑数字世界的未来

引言 随着物联网&#xff08;IoT&#xff09;设备的激增和5G网络的普及&#xff0c;我们正站在一个计算模式的新纪元门槛上——边缘计算。这一技术范式将数据处理和分析推向网络的边缘&#xff0c;即设备或终端&#xff0c;为实时性要求较高的应用提供了前所未有的可能性。 目…...

2024 前端面试题 附录3

这里记录的是昨天和今天原篇的知识点补充 原篇地址&#xff1a; 2024 前端面试题&#xff08;GPT回答 示例代码 解释&#xff09;No.41 - No.60 2024 前端面试题&#xff08;GPT回答 示例代码 解释&#xff09;No.61 - No.100 2024 前端面试题&#xff08;GPT回答 示例代…...

[Vue warn]: Duplicate keys detected: ‘1‘. This may cause an update error.

[Vue warn]: Duplicate keys detected: ‘1‘. This may cause an update error.——> Vue报错&#xff0c;key关键字不唯一&#xff1a; 解决办法&#xff1a;修改一下重复的id值&#xff01;&#xff01;&#xff01;...

Docker-Learn(二)保存、导入、使用Docker镜像

1.保存镜像 根据上一节内容&#xff0c;将创建好镜像进行保存&#xff0c;需要退出当前的已经在运行的docer命令行中断里面&#xff0c;可以通过在终端里面输入指令exit或者按下键盘上的 ctrlD建退出&#xff1a; 回到自己的终端里面&#xff0c;输入指令&#xff1a; docker…...

第三百一十五回

文章目录 1. 概念介绍2. 基本用法3. 补充用法4. 内容总结 我们在上一章回中介绍了"再谈ListView中的分隔线"&#xff0c;本章回中将介绍showMenu的用法.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在第一百六十三回中介绍了showMenu相关的内容…...

区块链(一): 以太坊基础知识

目录 什么是区块链&#xff1f;什么是以太坊&#xff1f;什么是加密货币&#xff1f;以太坊与比特币有什么不同&#xff1f;以太坊能做什么&#xff1f;什么是智能合约&#xff1f;以太坊社区以太坊白皮书 什么是区块链&#xff1f; 区块链是一个交易数据库&#xff0c;在网络…...

高级FPGA开发之基础协议PCIe

基础协议之PCIe部分 一、TLP包的包头 在PCIe的系统中&#xff0c;tlp包的包头的结构有许多部分是相似的&#xff0c;通过掌握这些常规的包头&#xff0c;能帮助理解在PCIe总线上各个设备之间如何进行数据的收发。 通用的字段 通用字段作用Fmt决定了包头是3DW还是3DW&#xff…...

Vue核心基础1:数据代理

1 回顾Object.defineProperty方法 let str hello const person {name: 张三,age: 18 } Object.defineProperty(person, sex, {// value: 男,// enumerable: true, // 控制属性是否可以枚举&#xff0c;默认值是false// writable: true, // 控制属性是否可以被修改&#xff0…...

12 ABC串口接收原理与思路

1. 串口接收原理 基本原理&#xff1a;通过数据起始位判断要是否要开始接收的数据&#xff0c;通过采样的方式确定每一位数据是0还是1。 如何判断数据起始位到来&#xff1a;通过边沿检测电路检测起始信号的下降沿 如何采样&#xff1a;一位数据采多次&#xff0c;统计得到高…...

leetcode(二分查找)34.在排序数组中查找元素的第一个和最后一个位置(C++详细解释)DAY11

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&#xff0c;返回 [-1, -1]。 你必须设计…...

算法刷题框架

前言&#xff1a;最近积累了一些算法题量&#xff0c;正在刷东神的算法笔记&#xff0c;监督自己记录下读后启发&#xff0c;顺便帮助道友们阅读 数据结构 这一部分老生常谈&#xff0c;数据的存储方式只有顺序存储和链式存储。 最基本的数组和链表对应这两者&#xff0c;栈…...

跟着cherno手搓游戏引擎【24】开启2D引擎前的项目总结(包括前置知识汇总)

前置技术&#xff1a; c动态链接和静态链接&#xff1a; 隐藏的细节&#xff1a;编译与链接_哔哩哔哩_bilibili 【底层】动态链接库(dll)是如何工作的&#xff1f;_哔哩哔哩_bilibili 预编译&#xff0c;编译&#xff0c;汇编&#xff0c;链接 预编译头文件&#xff1a; 为…...

石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP

一、石子合并 (经典例题) 设有 N 堆石子排成一排&#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量&#xff0c;可以用一个整数来描述&#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆&#xff0c;合并的代价为这两堆石子的质量之和&#xff0c;…...

IMX6ULL移植U-Boot 2022.04

目录 目录 1.编译环境以及uboot版本 2.默认编译测试 3.uboot中新增自己的开发板 3.编译测试 4.烧录测试 5.patch文件 1.编译环境以及uboot版本 宿主机Debian12u-boot版本lf_v2022.04 ; git 连接GitHub - nxp-imx/uboot-imx: i.MX U-Boot交叉编译工具gcc-arm-10.3-2021.0…...

ES实战-高级聚合

多桶型聚合 1.词条聚合–terms 2.范围聚合–range 3,直方图聚合–histogram/日期直方图 4.嵌套聚合 5.地理距离聚合 include(包含)exclude(不包含) GET /get-together/_search?pretty {"size": 0,"aggs": {"tags": {"terms": {"…...

网络安全产品之认识蜜罐

文章目录 一、什么是蜜罐二、蜜罐的主要类型三、蜜罐的主要功能四、蜜罐的主要组成及核心技术五、蜜罐的优缺点六、蜜罐如何与其他安全工具协同工作&#xff1f;七、什么是“蜜网”&#xff1f;与蜜罐的联系和区别是什么&#xff1f; 蜜罐的概念首次由Clifford Stoll在其1988年…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...