CF468C 题解

· · 题解

构造个锤头，为啥不直接退火．

我们设函数 F(n) 为 f(n) 的前缀和对 a 取模，即

F(n) = (\sum_{i=1}^n f(i)) \bmod a.

题意转化为，找到整数对 (i,j) 满足 i \ne j 且 F(i) = F(j)．

观察到这个 F 的图像就很像若干段从零上升到 a 然后再突变为 0 的曲线．

我们发现这个 F 有地方会突变为零，性质不是很好，考虑设 g(i) = |F(i) - \lfloor a/2 \rfloor|．这个 g 的图像就会变成一堆 W 形收尾拼接起来．我们固定 i,j 都在 g 的极小值处取得．注意到由于 f(i) 的值是 O(\log i) 级别的，也就是说，g(i) 的局部最小值只会取到 [0, O(\log a)] 范围．根据抽屉原理，g 的极小值只有 O(\log a) 种不同的取值．考虑不断跑模拟退火求出这个函数的随机一个极小值点，然后判断这个位置 F 的取值是否和之前跑到过的位置相等．

尝试分析这个做法的时间复杂度．首先显然可以使用数位 dp 或者直接计算每一位贡献等方式，以 O(\log i) 的时间复杂度单点求 g(i)．又由于 g 函数在极小值处附近的上升下降的趋势明显，模拟退火在求这种函数的极值时非常高效，几乎可以看作三分，因为我们认为模拟退火的复杂度为 O(\log a)．再算上模拟退火最多跑 O(\log a) 次，最终的的时间复杂度为 O((\log a)^3)．实际上远远跑不到这个上界．

代码参考见 原始 OJ 提交．