每日一题~abc356(对于一串连续数字 找规律,开数值桶算贡献)
添加链接描述
题意:对于给定的n,m 。计算0~n 每一个数和m & 之后,得到的数 的二进制中 1的个数的和。
一位一位的算。最多是60位。
我们只需要计算 在 1-n这些数上,有多少个数 第i位 为1.
因为是连续的自然数,每一位上1 的出现 必然存在某种规律。
我们从 第零位 开始计数。
第 i 位 的 1 的出现周期是 2^(i+1) ,其中前一半是0,后一半是1.(数量是 2^i个)
想明白这一点之后,
对于整除的那一部分,第i位的贡献是
int w=(long long )1<<i;
n/(w*2)*w
那么整的部分算完了,接下来算 散 的那一部分
这里可以自己找个例子,算一下。不然很容易错。
max((long long )0,n%(2*w)-w+1)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
signed main()
{int n,m;cin>>n>>m;int ans=0;for (int i=0;i<60;i++){if (m>>i &1){int w=(long long )1<<i;ans+=n/(w*2)*w+max((long long )0,n%(2*w)-w+1);ans%=mod;}}cout<<ans<<endl;return 0;
}
可以注意到
ai的数值非常小,不到1e6,这个时候 就有很大可能 开数值桶。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int wc=1e6+5;
int a[wc],s[wc];signed main()
{int n;cin>>n;int t=0;for (int i=0;i<n;i++){cin>>t;a[t]++;}for (int i=1;i<=wc;i++){s[i]=s[i-1]+a[i];}int ans=0;for (int i=1;i<=wc;i++){ans+=a[i]*(a[i]-1)/2;//选择两个相同的数的贡献//枚举左端点 ,比枚举右端点好,因为右端点不一定正好到wc,//后面可能还有一些比a[i]大的数 for (int j=i;j<=wc;j+=i){ans+=a[i]*(j/i)*(s[min(wc,j+i-1)]-s[j==i?i:j-1]);非常优美的代码^_^} }cout<<ans<<"\n";return 0;
}
时间复杂度: 第二层for里面,因为每次都是 i 的倍数,并且有一个上界 wc,所以是调和级数的复杂度,
复杂度为 log wc。
总的复杂度为 wc* log wc
相关文章:

每日一题~abc356(对于一串连续数字 找规律,开数值桶算贡献)
添加链接描述 题意:对于给定的n,m 。计算0~n 每一个数和m & 之后,得到的数 的二进制中 1的个数的和。 一位一位的算。最多是60位。 我们只需要计算 在 1-n这些数上,有多少个数 第i位 为1. 因为是连续的自然数,每一位上1 的…...

商业合作方案撰写指南:让你的提案脱颖而出的秘诀
作为一名策划人,撰写一份商业合作方案需要细致的规划和清晰的表达。 它是一个综合性的过程,需要策划人具备市场洞察力、分析能力和创意思维。 以下是能够帮助你撰写一份有效的商业合作方案的关键步骤和要点: 明确合作目标:设定…...

【MySQL】锁(黑马课程)
【MySQL】锁 0. 锁的考察点1. 概述1. 锁的分类1.1 属性分类1.2 粒度分类 2. 全局锁2.1 全局锁操作2.2.1 备份问题 3. 表级锁3.1 表锁3.2 语法3.3 表共享读锁(读锁)3.4 表独占写锁(写锁)3.5 元数据锁(meta data lock, MDL)3.6 意向…...

1.10编程基础之简单排序--02:奇数单增序列
OpenJudge - 02:奇数单增序列http://noi.openjudge.cn/ch0110/02/ 描述 给定一个长度为N(不大于500)的正整数序列,请将其中的所有奇数取出,并按升序输出。 输入 共2行: 第1行为 N; 第2行为 N 个正整数,其间用空格间隔。 输出 增序输出的奇数序列,数据之间以逗号间隔。数…...

【leetcode78-81贪心算法、技巧96-100】
贪心算法【78-81】 121.买卖股票的最佳时机 class Solution:def maxProfit(self, prices: List[int]) -> int:dp[[0,0] for _ in range(len(prices))] #dp[i][0]第i天持有股票,dp[i][1]第i天不持有股票dp[0][0] -prices[0]for i in range(1, len(prices)):dp[…...

IEC62056标准体系简介-4.IEC62056-53 COSEM应用层
为在通信介质中传输COSEM对象模型,IEC62056参照OSI参考模型,制定了简化的三层通信模型,包括应用层、数据链路层(或中间协议层)和物理层,如图6所示。COSEM应用层完成对COSEM对象的属性和方法的访问ÿ…...

嵌入式应用开发之代码整洁之道
前言:本系列教程旨在如何将自己的代码写的整洁,同时也希望小伙伴们懂如何把代码写脏,以备不时之需,同时本系列参考 正点原子 , C代码整洁之道,编写可读的代码艺术。 #好的代码的特点 好的代码应该都有着几…...
iwconfig iwpriv学习之路
iwconfig和iwpriv是两个常用的wifi调试工具,最近需要使用这两个工具完成某款wifi芯片的定频测试,俗话说好记性不如烂笔头,于是再此记录下iwconfig和iwpriv的使用方式。 -----再牛逼的梦想,也抵不住傻逼般的坚持! ----2…...

【Docker-compose】搭建php 环境
文章目录 Docker-compose容器编排1. 是什么2. 能干嘛3. 去哪下4. Compose 核心概念5. 实战 :linux 配置dns 服务器,搭建lemp环境(Nginx MySQL (MariaDB) PHP )要求6. 配置dns解析配置 lemp Docker-compose容器编排 1. 是什么 …...

【记录】LaTex|LaTex 代码片段 Listings 添加带圆圈数字标号的箭头(又名 LaTex Tikz 库画箭头的简要介绍)
文章目录 前言注意事项1 Tikz 的调用方法:newcommand2 标号圆圈数字的添加方式:\large{\textcircled{\small{1}}}\normalsize3 快速掌握 Tikz 箭头写法:插入点相对位移标号node3.1 第一张图:插入点相对位移3.2 第二张图࿱…...
《框架封装 · Redis 事件监听》
📢 大家好,我是 【战神刘玉栋】,有10多年的研发经验,致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久,希望大家多多支持,后续会继续提升文章质量,绝不滥竽充数…...
小白学webgl合集-Three.js加载器
THREE.TextureLoader: 用途: 加载单个图像文件并将其作为纹理应用到材质上。示例: const loader new THREE.DataTextureLoader(); loader.load(path/to/data.bin, function (texture) {const material new THREE.MeshBasicMaterial({ map: texture });const geometry new TH…...
【算法】字符串的排列
难度:中等 给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。 换句话说,s1 的排列之一是 s2 的 子串 。 示例 1: 输入:…...
5-3.损失函数
文章最前: 我是Octopus,这个名字来源于我的中文名–章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的…...

SCSA第四天
ASPF FTP --- 文件传输协议 Tftp --- 简单文件传输协议 FTP协议相较于Tftp协议 ---- 1,需要进行认证 2,拥有一套完整的命令集 用户认证 防火墙管理员认证 ---- 校验登录者身份合法性 用户认证 --- 上网行为管理中的一环 上网用户认证 --- 三层认证…...

品牌策划必读:9本改变游戏规则的营销经典
作为深耕品牌十余年的策划人,这些年自学啃下的书不计其数。 这里特意挑选了几本知名度不高但是却非常有用的“遗珠”优质品牌策划书籍分享出来。 如果你是一位初步了解品牌的人,这些书籍既包含了品牌理论基础,也有实用的实践指导。 这些书…...

泛型
背景 优点 类型绝对安全避免强制类型转换 泛型类 定义 使用 举例 泛型类 // 泛型类 T就是类型参数 public class Generic<T>{// key这个成员变量的类型为T,T的类型由外部指定private T t;public void set(T t){this.t t;}public T get(){return t;} }使用 // 创建一个泛…...
react动态渲染列表与函数式组件
1.如何使用jsx语法动态渲染列表呢,下边我用一个例子来切实总结一下 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scal…...

小程序内容管理系统设计
设计一个小程序内容管理系统(CMS)时,需要考虑以下几个关键方面来确保其功能完善、用户友好且高效: 1. 需求分析 目标用户:明确你的目标用户群体,比如企业、媒体、个人博主等,这将决定系统的功…...

HDFS 块重构和RedundancyMonitor详解
文章目录 1. 前言2 故障块的重构(Reconstruct)2.1 故障块的状态定义和各个状态的统计信息2.2 故障文件块的查找收集2.5.2.1 misReplica的检测2.5.2.2 延迟队列(postponedMisreplicatedBlocks)的构造和实现postponedMisreplicatedBlocks中Block的添加postponedMisreplicatedBloc…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...