CF1848F

__vector__ · 2023-07-23 20:30:58 · 个人记录

Vika 能不能让这场比赛难度分布正常一点

看到这题 *2400 以为是高大上算法。

其实只需要一个突破口。

设 f_{i,j} 是第 i 次操作后下标为 j 的数，把这个式子写下来并展开。

容易发现，一个 a 数列操作 2^k 次，第 i 个数就变成 a_i \oplus a_{(i+2^k) \bmod n}。

显然有解。

一个简单粗暴的做法，二分操作次数搞定。

O(n \log^2 n) 做法

后面更优做法待补充。