首页 > 编程语言 >2024“钉耙编程”中国大学生算法设计超级联赛(3) 1005 数论

2024“钉耙编程”中国大学生算法设计超级联赛(3) 1005 数论

时间:2024-07-30 20:07:18浏览次数:14  
标签:钉耙 log sum 2024 四元组 端点 1005 gcd

题意:

分析:

远看数论题,实则是道数据结构。

记 \(f_{i}\) 表示 \(r_{k}=i\) 的方案数,\(g_{i}\) 表示 \(l_{1}=i\) 的方案数,那么运用简单容斥,可得:

\[ans_{x} = (\sum_{i=1}^{n} f_{i}) - ((\sum_{i=1}^{x-1}f_{i})+1) \times ((\sum_{i=x+1}^{n}g_{i})+1)+1 \]

先考虑如何计算 \(f_{i}\),对于一个相同的 \(i\):

记 \(z=\gcd(a_{x},a_{x+1},\dots,a_{i})\),可以发现随着 \(x\) 变小,\(z\) 单调不升且 \(z\) 的本质不同的值不超过 \(\log V\) 个。因此可以使用二分把所有 \(z\) 相同的左端点的区间求出来,对于 \(z\) 相同的一段左端点 \(x \in [l,r]\) 而言,它在 \(dp\) 转移时必须满足上一个区间的 \(gcd\) 与这个区间的 \(gcd\) 值相等,解决方法也不难,只需要先二分离线预处理出一些四元组:

\[(l,r,i,z) \]

其表示左端点所属的区间为 \([l,r]\),右端点为 \(i\),\(gcd\) 为 \(z\)。根据上面的分析,这样的四元组的个数不超过 \(n \log V\) 个。我们将 \(z\) 相同的四元组按 \(i\) 排序,记 \(sum_{i}\) 表示在该 \(gcd\) 下 \(\sum_{j=1}^{i}f_{i}\),那么转移为:

\[(\sum_{j=l-1}^{r-1} g_{j}) \to f_{i} \]

转移它可以使用线段树(不用树状数组是因为树状数组无法快速清空),套路地维护 \(f_{i}\) 和 \(if_{i}\) 的前缀和,这样就能快速求出 \(g_{j}\) 的前缀和,这样就能转移了。总时间复杂度 \(O(n \log n \log V)\)。

标签:钉耙,log,sum,2024,四元组,端点,1005,gcd
From: https://www.cnblogs.com/xcs123/p/18333257

相关文章

  • c语言笔记(2024.7.24)第三天
    常量与变量概念:·表面:程序运行过程中取值可以改变的数据·实际:变量其实代表了一块内存区域/单元/空间。变量名可视为该区域的标识。整个变量分为三部分:·变量名:这个只是变量的一个标识,我们借助变量名来存取数据。·变量空间/存储单元:这个就是内存中分配的一块用来存放......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(1)1012并
    题目大意:给出n个矩形,求被k个矩形覆盖的面积的并集的期望,输出k为1-n的所一答案思路:由于是求期望所以是求出所有情况的和再除以可能的情况,每一种情况中的面积都由--同时被1个矩形覆盖,同时被两个矩形覆盖······同时被k个矩形覆盖组成,而且不难得出当k一定时,取被m个矩形覆盖的......
  • 【调试笔记-20240730-Linux-OpenWrt 23.05 安装 Docker 配置 bitnami/Wordpress-with-
    调试笔记-系列文章目录调试笔记-20240730-Linux-OpenWrt23.05安装Docker配置bitnami/Wordpress-with-NGINX实现微信用户在线注册登录文章目录调试笔记-系列文章目录调试笔记-20240730-Linux-OpenWrt23.05安装Docker配置bitnami/Wordpress-with-NGINX实现......
  • 2024-7-30 信友队模考总结
    开考这次的题目看着比较简单,第一题一眼前缀和,第二题是双指针,三四题不很一眼,感觉可以冲300pts。果然T1直接秒掉,J组难度。开写第二题感觉是双指针,而且也很有单调性,但是怎么实现并没有一下想出来,写了大概10min过了样例和自测,但是观摩的时候发现假了,我写的是伪双指针,\(\math......
  • 企业常用源代码加密软件,2024五款源代码加密软件推荐
    在现代企业中,源代码是核心资产之一,其安全性对企业的竞争力和创新能力至关重要。为了防止代码泄露和未经授权的访问,许多企业选择使用源代码加密软件。以下是2024年五款值得推荐的源代码加密软件,为企业提供可靠的安全保障。1.安秉源代码加密软件安秉源代码加密软件是一款专为......
  • 2024夏令营CTF部分wp
    misc前面几题基本来源于这篇文章>https://blog.csdn.net/qq_45894840/article/details/128346180?spm=1001.2014.3001.5502算是misc的入门级题目,就不多说了1.easy_stego_1是盲水印分离的题目首先拿到题目附件>http://nnd.edaker.com:8999/directlink/2/misc_easy_stego_1.p......
  • 2024 年求职不易,有没有什么效率高的求职方法?
    对于很多打工人来说,今年过得并不容易,不管是打工还是求职,都感觉艰难许多。市场竞争力变大,让许多打工人都感受到了浓浓的“求职焦虑”。对于应届生而言,今年更是具有挑战性的一年,毕业人数量高达1179万人,又创历史新高,毕业生的增多,就意味着就业竞争压力更大…在这样的就业形势下,最......
  • 【往届会后三个半月内EI检索 | EI会议征稿 】第四届物联网与机器学习国际学术会议(IoTM
     第四届物联网与机器学习国际学术会议(IoTML2024)20244th InternationalConferenceonInternetofThingsandMachineLearning重要信息大会时间:2024年8月9-11日         大会地点:中国-南昌        大会官网:www.iotml.cn   会......
  • 2024口碑最好五大骑行耳机精选,实测体验在线分享!
    作为有着多年骑行经验的数码博主,我深刻的明白,在骑行过程中,选择一款合适的耳机至关重要,一款合适的骑行耳机不仅可以增加骑行中的体验,还能保证骑行中的安全,骨传导耳机凭借不入耳佩戴更健康,以及开放式听音等优点成为众多骑行爱好者的首要选择。但随着骨传导耳机热度增加,市面上开始......
  • 2024.7.30 test
    A有一个数\(n\)和\(m\)种操作,第\(i\)次操作使得\(n\getsn/A_i\),问最多遍历多少个数。\(n\le10^5,m\le10\)。不难发现暴力即可通过。B给定集合\(S\),对于每个\(i\in[1,m]\)你需要求出选择数最多和最少的值使得\(\gcd=i\)。\(n,S_i\le3e5\)。首先对于每个\(i......