题解-CF1205E
2021/7/14 23:50:59
本文主要是介绍题解-CF1205E,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这题完全体现了我的 数学推导 能力有多差。
中间还被 alpha 教育了,我不会算这个复杂度/kk
\[O(\sum_{i=1}^{n} \sum_{j|i}\sum_{k|\frac{i}{j}}1)=O(n\log^2n) \]根据一些等价我们得到下面的式子。(上面是字符串和图论的部分,下面就全是数学推导了)
\[ans\times k^n=\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}k^{\max{\gcd(i,j), i+j-n}} \]然后有一个不太能扩展的 \(O(n\log^2n)\) 做法。
考虑枚举 \(\gcd(i,j)\) 和 \(i+j\),然后计算同时满足 \(i,j\) 组数。
\[\begin{aligned} ans\times k^n&=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=d][i+j=s]\\ &=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i=1}^{n-1}[\gcd(i,s-i)=d]\\ &=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i=1}^{[\frac{n-1}{d}]}[\gcd(i,\frac{s}{d}-i)=1]\\ &=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i|\frac{s}{d}}\mu(i)\sum_{j=ik}1 \end{aligned} \]然后上面的式子有一个缺陷,就是 \(i,j\) 的范围没有表示。
\[1\le i\le n-1\\ 1\le s-i\le n-1\\ \Rightarrow s+1-n\le i\le s-1\\ \]然后令 \(a=\max\{1,\frac{s}{d}-[\frac{n-1}{d}]\},b=\min\{\frac{[n-1]}{d},\frac{s}{d}-1\}\),有最终的式子 \(ans\times k^n=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i|\frac{s}{d}}\mu(i)([\frac{b}{i}]-[\frac{a-1}{i}])\)。
还有一个常见的 \(O(n\logn)\) 算法和一个 \(O(n)\) 算法。看懂了但是不想写了(咕咕有空就补),可以在下面的题解里看到。
reference
木xx木大的 luogu 题解
这篇关于题解-CF1205E的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解