CF1601F Two Sorts
CF1601F Two Sorts
给定 \(n\),将 \(1\sim n\) 按照字典序排序,\(a_i\) 表示第 \(i\) 小的数,求:
\]
\(1\le n\le 10^{12}\)
Solution
先暴力,我们按照字典序搜索(记 \(\text{cnt}\) 和 \(\text{val}\) 表示第 \(\text{cnt}\) 小的数是 \(\text{val}\))即可线性。
考虑根号分治(不搜索末 \(6\) 位),我们同样搜索,处理到 \(\overline {\text{valxxxxxx}}\) 时(假设 \(\overline{\text{val999999}} \le n\),即没有任何上界限制),会发现可以快速计算这些值的和。
我们记 \(cnt_{x}\) 表示 \(x\) 的排名,\(cnt'_x\) 表示 \(x\) 在 \(\overline {abcdef}\) (\(0\le a,b,c,d,e,f\le 9\),即可以有前导零)的排名。
那么, \(cnt_{\overline {\text{valxxxxxx}}}=cnt_{\overline{\text{val}}}+cnt'_{\overline{\text{xxxxxx}}}\),因此可以把贡献拆成:
\]
因此,我们可以预处理 \(\overline{\text{xxxxxx}}\) 相关的信息,即 \((cnt'_{\overline{\text{xxxxxx}}}-\overline{\text{xxxxxx}})\)。
由于上述式子是 \((A+B)\bmod P\) 形式,而 \(0\le A,B<P\),因此值为 \(A+B\) 或 \(A+B-P\),判断这个可以通过一个二分解决。
因此,总时间复杂度 \(\mathcal O(\sqrt{n} \log n)\)。
提一句,这个实在太难表述了,所以可以对照代码阅读。我的代码码量极小,并且是目前的最优解。
最新文章
- Python强化训练笔记(七)——使用deque队列以及将对象保存为文件
- OpenCv编程
- js-比较两个日期的大小
- [转载]JavaEE学习篇之——Session&;&;Cookie
- [LintCode] Roman to Integer 罗马数字转化成整数
- IE10、IE11解决不能播放Flash的问题!
- Android 开发前的基本的配置及第一个Android 程序
- Google Polymer以及Web UI框架
- MyBatis中井号与美元符号的区别
- JDK1.8 HashMap中put源码分析
- JavaBean学习--练习示例
- 5.1.1 读取Redis 数据
- Undefined class constant &#39;MYSQL_ATTR_USE_BUFFERED_QUERY&#39;
- Google Dremel 原理 - 如何能3秒分析1PB
- java类成员变量与代码块初始化
- [SCOI 2010]传送带
- SpringMvc 这篇文章写得不错 多多学习2017.6.29
- SRE_ Google运维解密
- bitmap的使用
- webpack学习笔记--区分环境
热门文章
- 第一天&#183;浏览器内核及Web标准
- jboss7学习3-jboss安装 访问(外网)添加用户
- JavaScript遍历表单元素
- 论文解读(Graph-MLP)《Graph-MLP: Node Classification without Message Passing in Graph》
- [ SOS ] 版本控制工具 笔记
- Vue src动态引入图片不显示问题
- datasets数据读取器
- hashlib加密模块、logging日志模块
- springdata jpa多表查询的方式
- 【大学物理实验】01 单摆测重力加速度 的 g 计算代码