题解：CF1743G Antifibonacci Cut

· · 题解

做法一

考虑没有 4MB 的空间限制怎么做。

值不超过 m 的斐波那契数是 O(\log m) 级别的，直接 dp，用总的 dp 值减掉不合法的，问题在于判定区间的字符串是不是斐波那契串。

在不卡空间的情况下可使用哈希简单维护，但不具有拓展性。考虑令 f_i 表示以 i 结尾的最长斐波那契串，那么长度为 f_i\bmod 2,\cdots,f_i-2,f_i 都是以 i 结尾的斐波那契串。递推 f 是简单的。

因为 0\le f_i<32，因此恰好可以用 5 个 bit 来记录，算上存原来的字符串又有 1 个 bit，总共 6 个 bit，需要 2MB 的空间。

但是关键问题在于 dp 部分。如果对于每个点都永久存储 dp 值，就需要 m 个 int，并不能接受。

这里给出一个结论：如果一个 dp 值之后不会被调用了，则在使用期结束的时刻删除，则任意时刻需要存储的 dp 值是 O(\log n) 级别的。证明不表。

空间复杂度 7m 个 bit。

https://codeforces.com/contest/1743/submission/344440248。

做法二

考虑维护所有 j 满足 S[j,i] 是斐波那契串前缀，每次暴力求出这个点应该填什么。

空间复杂度 O(\log n)。