September 18, 2024
询问区间不同元素数目有各种经典离线和函数式线段树做法，但是这个题要统计整体，直接上数据结构复杂度反而不太对。
我们可以单独统计每种元素对答案的贡献，而这个只要计算其补集即可，复杂度 O(n)。
https://atcoder.jp/contests/abc371/submissions/57884316
原题等价于求字典序最小的 AP^x，由于 P 是个排列，显然可以只考察它的循环分解。我们从左到右贪心的确定 AP^x 的每一位以及打包得到其所在的循环所有位置的结果，按顺序考察每一组这样的循环。我们总能得到一组形如 x = r (mod c) 的限制，这里的 c 是循环的长度，我们要在贪心结果尽可能小的同时，不破坏之前得到的所有限制条件。
我们可以合并这些条件，计算所有这些 c 形成的 lcm，但是这样这个 lcm 可能会特别大。注意到我们并不需要计算具体的 x，并且对于所有互素的 c，显然这些限制是不互相影响的，这提醒我们只需要考察和更新所有 c 的因子所形成的限制条件，进一步我们只需要维护所有素数幂的限制即可。
https://atcoder.jp/contests/abc371/submissions/57872303
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。