传送门:https://atcoder.jp/contests/arc064
感觉前几题质量一般般。。但F还不错的
C.贪心水
D.博弈水
最开始还以为是判相等的字符之间的长度来等价组合游戏,但是它很重要的一点是最外面两个字符无法拿去,所以容易看出只与【最外面两个字母相等与否】 以及 【n的奇偶性】有关.
E.最短路水
容易建图跑最短路,注意精度问题,它要求精确到 1e-9.那么需要使用long double 来储存。
F. 质因分解 + 容斥原理 + 字符串(好题)
题目大意:给你一个长度为n的序列。序列的每个数取值都为 从 1 ~ k.生成所有回文串,对于每个回文串,将它的每一个前缀放到字符串末尾可以得到[串长]个字符串。现在让你统计本质不同的字符串的个数。
题解:
分解问题,若没有取前缀的操作,它能够生成 个本质不同回文串。
考虑每个回文串取每个前缀能够对答案贡献多少答案。
最自然的想法,答案就是. 但是考虑该样例:
上述样例只能贡献三个本质不同的回文串。自然想到 最小循环节
结论:容易证明:回文串的最小循环节还是回文串。
自然想到枚举最小循环节:最小循环节一定是n的因数,所以的枚举循环节.
但是还有一个问题:在求最小循环节回文串,它也会存在重复贡献的问题。
例如:我们在求最小循环节 为 6 的 回文串时,会将最小循环节为 3 的回文串也统计进去。
所以这里提出一种的容斥原理:
最小循环节为6的回文串 = 循环节长度为6的回文串 - 最小循环节为2的回文串 - 最小循环节为3的回文串
所以我们对n质因分解后,将因数排序(因数具有传递性),令为循环节长度为i的回文串。
接下来从小到大枚举因数,对dp做容斥.
. 这个时候
就代表 最小循环节长度为i的回文串的方案数,
最后考虑回文串对答案的贡献:
每个奇数长的最小循环节对答案贡献为它的长度
画画图容易看出,每个偶数长的最小循环节对答案贡献为它的长度的一半。
本质:容斥求最小循环节
拓展:求一个长度为n的只含大小写字母的字符串中,有多少个含有长度为X的最小循环节的字符串的个数.