板刷计划:ARC064

传送门:https://atcoder.jp/contests/arc064

感觉前几题质量一般般。。但F还不错的

C.贪心水

D.博弈水

最开始还以为是判相等的字符之间的长度来等价组合游戏,但是它很重要的一点是最外面两个字符无法拿去,所以容易看出只与【最外面两个字母相等与否】 以及 【n的奇偶性】有关.

E.最短路水

容易建图跑最短路,注意精度问题,它要求精确到 1e-9.那么需要使用long double 来储存。

F. 质因分解 + 容斥原理 + 字符串(好题)

题目大意:给你一个长度为n的序列。序列的每个数取值都为 从 1 ~ k.生成所有回文串,对于每个回文串,将它的每一个前缀放到字符串末尾可以得到[串长]个字符串。现在让你统计本质不同的字符串的个数。

n \leq 1e9

题解:

分解问题,若没有取前缀的操作,它能够生成 k^{\lceil  \frac{n}{2} \rceil } 个本质不同回文串。

考虑每个回文串取每个前缀能够对答案贡献多少答案。

最自然的想法,答案就是k^{\lceil  \frac{n}{2} \rceil }*n . 但是考虑该样例:121\ 121\ 121

上述样例只能贡献三个本质不同的回文串。自然想到 最小循环节

结论:容易证明:回文串的最小循环节还是回文串。

自然想到枚举最小循环节:最小循环节一定是n的因数,所以O(\sqrt{n})的枚举循环节.

但是还有一个问题:在求最小循环节回文串,它也会存在重复贡献的问题。

例如:我们在求最小循环节 为 6 的 回文串时,会将最小循环节为 3 的回文串也统计进去。

所以这里提出一种O(n^2)的容斥原理:

最小循环节为6的回文串 = 循环节长度为6的回文串 - 最小循环节为2的回文串 - 最小循环节为3的回文串

所以我们对n质因分解后,将因数排序(因数具有传递性),令dp(i)为循环节长度为i的回文串。

dp(i) = k^{\lceil  \frac{i}{2} \rceil }*i

接下来从小到大枚举因数,对dp做n^2容斥.

dp(i)-=\sum_{i|j} dp(j). 这个时候dp(i)就代表 最小循环节长度为i的回文串的方案数,

最后考虑回文串对答案的贡献: 

每个奇数长的最小循环节对答案贡献为它的长度

画画图容易看出,每个偶数长的最小循环节对答案贡献为它的长度的一半。

本质:容斥求最小循环节

拓展:求一个长度为n的只含大小写字母的字符串中,有多少个含有长度为X的最小循环节的字符串的个数.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。