Volume 12

551. Sum of digits sequence

令表示的数位和, 考虑, 那么只要, 其实, 其中.

不妨令表示从开始, 根据递推式, 直到的最小, 以及当前的值(的值是一个pair).

的转移比较容易, 考虑枚举当前最高位的数字, 那么可以从转移过来, 具体来说, . 初始边界值是.

知道了数组之后, 我们显然就可以通过从高到低依次枚举的每一位来确定.

552. Chinese leftovers II

这个题实际上就是要求. 令为前个素数的乘积, 那么有下面一个同余方程:

不妨令, 那么可以得到.

那么假设我们得到了的值, 显然就可以递推出的值了. 由于以内只有个素数, 于是可以直接暴力更新.

553. Power sets of power sets

令表示选出来集合的并恰好有种不同数字, 且分成了个连通分量的方案数. 显然. 考虑如何计算, 一个显然的递推式就是, 表示单独拿出来一个大小为的联通块, 为了不重复计数, 这个联通块必须包含最小的数. 剩下的问题就是如何计算了.

令表示选出若干集合, 他们的并是全集的方案数, 这个打了下表可以知道就是A003465, 于是. 知道了以后, 的式子就显而易见了.

这样我们就有了一个的算法, 滚动数组一下很快就跑出来了. 但是这题还可以用生成函数做的更好.

令, 定义三个生成函数, 和:

那么, 我们可以知道的生成函数是:

其中.

于是用FFT/NTT就可以在的复杂度解决了.

554. Centaurs on a chess board

可以考虑下题目中的是如何得到的. 考虑把的棋盘以为单位划分成, 那么显然任意一个的小块最多只能包含一个centaur. 于是一个的棋盘最多只能放个centaur. 然后通过简单的推导可以知道. 然后用lucas定理计算即可.

555. McCarthy 91 function

和之前的#340 Crazy Function一样, 可以知道这个东西是一个分段函数. 打个表就可以发现以为周期, 每个周期内是一个公差为的等差数列, 最高项是. 于是找不动点其实就是找一个区间, 使得, 化简下得到. 于是只要枚举, 然后再枚举就可以解出. 求出区间后就是一个等差数列求和的问题.

556. Squarefree Gaussian Integers

可以回想起#193的公式, 这个题稍微改下那个公式就好了: . 其中表示有多少proper Gaussian integer满足. 至于看着参考这个数列A120630.

557. Cutting triangles

根据梅涅劳斯定理, 可以得到, 枚举以及, 然后就可以计算出了.

558. Irrational base

这个题的方法有很多.

方法一

注意到是数列的特征方程. 我们知道有个Zeckendorf's theorem, 可以用Fibonacci数表示一个整数. 我们还知道有个Golden ratio base, 可以用base-来表示一个整数. 事实上base-和Fibonacci-base是可以对应的. 于是猜测可以用来代替. 为了处理出, 可以把一开始乘上一个较大的, 然后贪心做, 从打到小依次减过去, 当然需要保证相邻两项差大于等于. 这个算法的解释可以在论坛中看到, 这个以及这个.