每日一题~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…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...

大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...