Calculus 题解
注意到题中所给的所有函数均为发散。所以只需要检查是否所有的构成函数的系数均为 0 即可。
Kanade Loves Maze Designing 题解
注意到允许一个 的算法，考虑用 +-1 法统计每种颜色即可。即，记 为颜色 的出现次数，
为从某点处开始 DFS，到点 得到的答案，进入该点时，给 加一，如果这种颜色第一次出现，则给
加一，记录答案，退出该点时，如果给 减一后这种颜色不会出现，则 减一。
时间复杂度： ，空间复杂度： 。
关键词：DFS
Cycle Binary 题解
对于一个字符串 ，如果我们将其表示为如题目所述的 的形式，则称 为 的一个循环
节， 的长度为 的一个周期。
题目要求我们对所有长度为 的 01 串，按其最小周期分类计算贡献。设 表示长度为 ，最小周
期为 的 01 串的个数，则我们要求的是（设为 ）：
首先考虑如何求 。长度为 的 01 串一共有 个，其中，存在周期 满足 且 的串显
然不能计算在 内，因为其有更小的周期 。我们很自然地作出以下猜想：
等于长度为 的 01 串中，所有不存在周期 满足 且 的串的个数。
为了验证上述猜想，我们需要用到 周期引理（Periodicity Lemma）：
设字符串 有周期 和 ，满足 ，那么 也是 的一个周
期。
设有长度为 的 01 串 和长度为 的 01 串 ， 不存在周期 满足 且 。
假设 存在一个比 更小的周期 ，由周期引理：
1. 如果 ，则 也是 的周期。同时 ， 也
是 的一个周期，这与 不存在周期 满足 且 相矛盾。故假设不成立， 就是 的
最小周期，我们的猜想正确，并得到 的计算公式：
2. 如果 ，我们无法通过周期引理来证明之前的猜想。
在情况 1 中， 满足的条件等价于 。对于情况 2，观察式 可以发现，
的 系数都是 ，于是我们不需要分别计算这些 ，用总串数 减去
的 之和即可。式 可化为：
评论0
最新资源