首页 > 其他分享 >MX Weekly 赛时/VP 记录

MX Weekly 赛时/VP 记录

时间:2024-08-14 12:18:57浏览次数:14  
标签:le 赛时 limits sum mid VP oplus MX gcd

感觉题目质量比较高,所以挖了个坑((。

X2

前三题简单不写

洛谷 - P10855

傻逼赛时想出两种正确思路都他妈的没仔细想,真糖丸了

不妨将题目中要求的式子化简。

\[\begin{equation} \begin{split} \sum\limits_{i=1}^n\sum\limits_{j=1}^i \gcd(j,i\oplus j)^k&= \sum\limits_{j=1}^n\sum\limits_{i=j}^n \gcd(j,i\oplus j)^k\\ &=\sum\limits_{j=1}^n\sum\limits_{x=1}^{\min(2^{18}-1,2n)} \gcd(j,x)^k[j\le x\oplus j \le n] \\ &=\sum\limits_{d=1}^nd^k\sum\limits_{j=1}^ n\sum\limits_{x=1}^{\min(2^{18}-1,2n)} [d\mid j][d\mid x][j\le x\oplus j \le n] \\ \end{split} \end{equation} \]

不妨记 \(f_d\) 为 $\sum\limits_{j=1}^ n\sum\limits_{x=1}{\min(2-1,2n)} [d\mid j][d\mid x][j\le x\oplus j \le n] $,本质上表示合法的 \(d\mid \gcd(j,x)\) 的数量,记 \(g_d\) 为合法的 \(d=\gcd(j,x)\) 的数量,有 \(g_d=f_d-\sum\limits_{i=1}^n g_i[d\mid i]\)。

考虑如何计算 \(f_d\) ,有异或操作通常在 Trie 上进行操作,将所有合法的 \(x\) 加入 Trie 中,将 \([j\le x\oplus j \le n]\) 差分,只统计 \([x\oplus j \le r]\) 两遍即可,而这是较为容易的,具体见代码。

总复杂度为 \( \mathcal{O}(\sum\limits_{i=1}^n \frac{n}{i}\times \log n)= \mathcal{O}(n\log^2n)\),可以通过此题。

洛谷 - P10856

怎么都说被出烂了,我怎么没见过??我怎么没见过??我怎么没见过??我怎么没见过??我怎么没见过??我怎么没见过??

若在一次 2 操作前做了若干次 1 操作,我们可以看作只进行了一次 1 操作,因为有结合律。

有区间询问不妨使用线段树,注意到 \(n\) 为 2 的整数次幂,所以线段树的结构类似与 01-trie 的结构,左儿子表示当前这一位为 0 所包含的区间,右儿子表示当前这一位为 1 所包含的区间,一个结点内所有包含的位置的二进制前缀相同,即对于一段线段树上的区间 \([l,r]\),若其在第 \(i\) 层(从 0 开始,则 \([l,r]\) 二进制前 \(i\) 位相同,后面的位为 \([0,2^{(k-i)}-1]\)。

考虑修改操作 \(x\) 对于一段线段树区间 \([l,r]\) 的变换,不妨设区间 \([l,r]\) 的深度在第 \(i\) 层。

若 \(x\le r-l+1\),由上发现变换后原先的数还在 \([l,r]\) 中。

若 \(x\ge r-l+1\),由上发现 \([l,r]\) 的前缀改变了,转换成了另一个区间 \([l',r']\),且满足两个区间同层且 \([l,r]\) 的固定前缀 \(\oplus\) \(x\) 前 \(i\) 位 \(= [l',r']\) 的固定前缀! 那么\([l,r]\oplus x\) 变换为 \([l',r'] \oplus x后k-i位\)。

不妨预处理出 \(x\le r-l+1\) 的答案,答案的形式为 \(1+\sum a_{i}\neq a_{i+1}\),维护后者即可。总复杂度 \(O(n\log n)\)

洛谷 - P10857

本月找时间补

标签:le,赛时,limits,sum,mid,VP,oplus,MX,gcd
From: https://www.cnblogs.com/smilemask/p/18358638

相关文章

  • DeiT-LT:印度科学院提出针对长尾数据的`DeiT`升级模型 | CVPR 2024
    DeiT-LT为ViT在长尾数据集上的应用,通过蒸馏DIST标记引入CNN知识,以及使用分布外图像并重新加权蒸馏损失来增强对尾类的关注。此外,为了减轻过拟合,论文建议用经过SAM训练的CNN教师进行蒸馏,促使所有ViT块中DIST标记学习低秩泛化特征。经过DeiT-LT的训练方案,DIST标记成为尾类的专家,分......
  • StarNet:关于 Element-wise Multiplication 的高性能解释研究 | CVPR 2024
    论文揭示了staroperation(元素乘法)在无需加宽网络下,将输入映射到高维非线性特征空间的能力。基于此提出了StarNet,在紧凑的网络结构和较低的能耗下展示了令人印象深刻的性能和低延迟来源:晓飞的算法工程笔记公众号论文:RewritetheStars论文地址:https://arxiv.org/abs/240......
  • DRM:清华提出无偏差的新类发现与定位新方法 | CVPR 2024
    论文分析了现有的新类别发现和定位(NCDL)方法并确定了核心问题:目标检测器往往偏向已知的目标,忽略未知的目标。为了解决这个问题,论文提出了去偏差区域挖掘(DRM)方法,以互补的方式结合类无关RPN和类感知RPN进行目标定位,利用未标记数据的半监督对比学习来改进表征网络,以及采用简单高效的m......
  • 软件无线电系统 高速图像采集卡 设计原理图: 613-基于6UVPX C6678+XCVU9P的信号处理板
    基于6UVPXC6678+XCVU9P的信号处理板卡一、板卡概述      板卡基于6U VPX标准结构,包含一个C6678 DSP芯片,一个XCVU9P 高性能FPGA,双路HPC FMC。 二、处理板技术指标•  DSP处理器采用TI 8核处理器TMS320C6678;•  DSP 外挂一组64bit DDR3颗粒,总容量2GB,数据......
  • 了解经典的 MPLS L3VPN 网络架构
    1.多协议标签交换技术MPLS的概念        MPLS(Multi-ProtocolLabelSwitching,多协议标签交换技术),传统网络中就拥有了3种经典转发实现,它们分别是:L2交换转发L2.5标签转发L3路由转发        MPLS协议则作用于L2.5层,其将L3路由技术和L2交换技术相......
  • 无线仿真平台基带信号处理卡:612-基于6UVPX C6678+XCVU9P的4路2Gsps AD 8路2Gsps DA 信
    基于6UVPXC6678+XCVU9P的4路2GspsAD8路2GspsDA信号处理板卡   一、板卡概述      板卡基于6UVPX标准结构,包含一个C6678DSP芯片,一个XCVU9P高性能FPGA,8路DA,4路AD。 二、技术指标 ●  DSP处理器采用TI8核处理器TMS320C6678; ●  DSP外挂一组64......
  • mpls-vpn实验
    实验需求客户X及Y各自有2个站点,现需要通过MPLSVPN实现站点之间的互联,分别对应VPNX和VPNY。互联接口、AS号及IP地址信息如图,客户X站点与PE之间采用OSPF交互路由信息,客户Y站点与PE之间采用BGP交互路由信息。数据规划配置项描述PE1PE2VPN名称VPNXVPNYVPNXVPNYRD100:1200:1100......
  • 痞子衡嵌入式:探析i.MXRT1050在GPIO上增加RC延时电路后导致边沿中断误触发问题(上篇)
    大家好,我是痞子衡,是正经搞技术的痞子。今天痞子衡给大家分享的是i.MXRT1050在GPIO上增加RC延时电路后导致边沿中断误触发问题探析。前段时间有一个RT1052客户反馈了一个有趣的问题,他们设计得是一个带LCD屏交互的应用,应用以官方SDK里的lvgl_demo_widgets_bm例程......
  • Docker②_安装部署Anylink_VPN
    目录1.Anylink项目介绍2.Docker安装部署Anylink2.1安装Docker环境2.2 pull镜像2.3创建密码2.4修改自己的配置文件2.5 启动Anylink2.6Linux虚拟机开放端口2.6交换机防火墙对外开放ssl端口2.7 检查状态1.Anylink项目介绍        AnyLink是Tmax......
  • HTB-Permx靶机笔记
    Permx靶机笔记概述permx靶机是HTB的简单靶机,这台靶机整体考验渗透人员的信息搜集能力,可以收只有信息搜集的快速,才能快速拿到它的flag。整体是比较简单的靶机靶机连接:https://app.hackthebox.com/machines/PermX一、nmap扫描1)端口扫描nmap-sT--min-rate10000-p--......