笼中鸟

sidekick257 · 2024-01-14 21:20:09 · 题解

安利一下 Remember11，非常神作，值得一玩。

观察到 \forall i\in_{l+k,r},f_i=\sum_{j=1}^kf_{i-j}\Leftrightarrow \forall i\in_{l+k+1,r},f_i-f_{i-1}=f_{i-1}-f_{i-k-1}。

因为 i,i-1,i-k-1 体现在 [l+k,r] 上都是连续段，直接线段树维护模 p 意义下的哈希暴力判断是否两段区间相等即可。

然后要注意 r=l+k 的情况特判一下就行。

交换不同数列的区间容易想到可以写平衡树轻易的维护，但是平衡树太答辩了，在线段树上交换对应区间编号就可以了。

出题人代码写的太丑就不放了。

（PS：这题本来是 k=2 的，但是多亏了 良心 WA 题人 发现了 k=2 可以直接合并。）