FibonacciPartition - 题解
标签与难度
标签: 数据结构, set, 斐波那契, 数论, 贪心, 构造 难度: 2900
题目大意喵~
主人你好呀，这道题是关于斐波那契数列的一个有趣问题！喵~
首先，题目定义了一个斐波那契数列：
这个数列的前几项是 。
然后，对于一个正整数 ，我们定义 partition(n) 为：将 表示成不同的斐波那契数之和时，能够使用的最多的项数。 比如说，partition(6)=3，因为 可以表示成 ，这是用最多项的表示方法。
题目会给我们一个初始为 的整数 。接下来会有一系列操作，每次操作会给出两个数 和 ，我们要把 的值加上 。在每次操作之后，我们都需要计算并输出当前的 partition(x) 是多少。
简单来说，就是维护一个大数 ，在每次更新后，找出把它拆成不同斐波那e契数的和时，最多能拆成几项，呐。
解题思路分析
这道题真的很有挑战性呢，喵！直接处理一个可能非常大的数字 并计算它的 partition(x) 是不现实的。我们需要找到一种方法来表示 ，这种表示方法要能方便地进行加减法，并且能快速地计算出 partition(x)。
核心思想：寻找最优表示法
要想让斐波那契数的项数最多，我们的策略应该是“反过来”的 Zeckendorf 定理。Zeckendorf 定理告诉我们，任何正整数都可以唯一地表示为一组不相邻的斐波那契数之和，这通常是项数最少的表示。而我们想要项数最多，就要反其道而行之：尽量把大的斐波那契数换成小的。
我们有恒等式 。这意味着，只要我们的和里面有 但没有 和 ，我们就可以把 替换掉，增加一项。这个过程可以一直进行下去，直到无法再分解为止。
经过一番探索（和偷看了一点点答案，喵呜~），可以发现一个神奇的结论：任何正整数 都可以被唯一地表示为一堆“同奇偶性连续斐波那契数之和”的和。
这是什么意思呢？一个“同奇偶性连续斐波那契数”的片段，我们叫它“梳子”（comb），形如 ，其中所有下标的奇偶性相同。例如， 就是一个偶数梳子。
一个非常漂亮的性质是，这样一个梳子的和可以用一个简单的公式计算：
(这里我们需要定义 来让公式在边界情况下也成立）。
所以，任何数字 都可以表示成 的形式，其中 是一系列互不相交的梳子。这个表示是唯一的！
计算 partition(x)
当我们得到了这个“梳子表示法”，partition(x) 的值就可以通过一个公式计算出来。它等于所有梳子中斐波那契数的总数，再加上因分解梳子边界而额外产生的项数。
具体来说，partition(x) 的值是：
- 所有梳子
[l, r]的大小之和。一个梳子[l, r]的大小为 。 - 梳子之间的“间隙”产生的额外项。对于一个不是从 或 开始的梳子
[l, r]，它可以看作是从一个更大的斐波那契数分解而来的。这个分解过程会填补它与前一个梳子之间的间隙，从而产生更多的项。
这个计算方式有点复杂，但在代码中 MdfAns 函数实现了这个逻辑。它在每次插入或删除一个梳子时，动态地更新总答案。
维护梳子集合
现在，问题转化为了如何维护这个梳子的集合。每次操作 x += a * F_b，我们都需要更新这个集合。
第一步：分解 a * F_b
单个的 好办，但我们面对的是 。如果 很大，我们不能真的加 次 。这里需要一个“黑魔法”，就是把 本身也用一个类似斐波那契的数系来表示。利用 这样的恒等式，我们可以把任意整数 表示成 的形式。然后 就可以变成 的形式。
参考代码中的 ToModifies 函数做的就是这个工作。它是一个相当复杂的数论过程，把 分解成了一系列 的加减操作。我们可以暂时把它当成一个可靠的黑盒，它会告诉我们，一次 x += a * F_b 的操作等价于进行若干次 x += F_k 或 x -= F_k。
第二步：处理单个 的加减
现在我们只需要实现 Put(k) (加 ) 和 Take(k) (减 ) 这两个核心操作。这两个操作会修改我们维护的梳子集合。
Put(k) 的逻辑分析：
当我们执行 Put(k)，即向 中加入 时，有以下几种情况：
- 创造新梳子: 如果 和 都不在当前的和中，那么 就会形成一个自己的新梳子
[k, k]。 - 合并梳子:
- 如果 存在（即一个梳子以 结尾）， 会和它合并，将梳子
[l, k-2]扩展为[l, k]。 - 同理，如果 存在（一个梳子以 开始）， 会和它合并。
- 如果两边都存在，那么 会像一座桥梁，把两个梳子
[l1, k-2]和[k+2, r2]连接成一个大梳子[l1, r2]。
- 如果 存在（即一个梳子以 结尾）， 会和它合并，将梳子
- 梳子内加法 (最复杂的情况): 如果 已经存在于某个梳子
[l, r]中了（即 且 奇偶性相同），我们相当于执行了 。根据恒等式 ，我们需要：- 从原有的和中移除 。这会把梳子
[l, r]从 处断开，分裂成[l, k-2]和[k+2, r]两个小梳子。 - 然后，我们再加入 和 。这相当于递归调用
Put(k+1)和Put(k-2)。
- 从原有的和中移除 。这会把梳子
Take(k) 的逻辑与 Put(k) 相反，同样复杂，是它的逆操作。
总的来说，整个算法就是用 std::set 维护一堆梳子，然后通过一系列精巧的合并、分裂操作来响应 的更新。这只我的爪子都快算不过来了，喵~ 但只要理清了这些情况，我们就可以写出代码啦！
代码实现
这是我根据上面的思路，重新整理和注释的代码。希望能帮助你理解这个精妙的过程，喵~
cpp
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
// 使用快读模板
namespace io {
const int BUF_SIZE = 1 << 21 | 1;
char in_buf[BUF_SIZE], *in_s, *in_t, out_buf[BUF_SIZE], *out_s = out_buf, *out_t = out_s + BUF_SIZE - 1;
int f, t;
char c, ch[100];
#define GET_CHAR() (in_s == in_t ? (in_t = (in_s = in_buf) + fread(in_buf, 1, BUF_SIZE, stdin), in_s == in_t ? EOF : *in_s++) : *in_s++)
inline void flush() {
fwrite(out_buf, 1, out_s - out_buf, stdout);
out_s = out_buf;
}
inline void put_char(char x) {
*out_s++ = x;
if (out_s == out_t) flush();
}
template <class T>
inline void read(T &x) {
for (f = 1, c = GET_CHAR(); c < '0' || c > '9'; c = GET_CHAR()) if (c == '-') f = -1;
for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = GET_CHAR());
x *= f;
}
template <class T>
inline void print(T x, char k = '\n') {
if (!x) put_char('0');
if (x < 0) put_char('-'), x = -x;
while (x) ch[++t] = x % 10 + '0', x /= 10;
while (t) put_char(ch[t--]);
put_char(k);
}
struct Flusher { ~Flusher() { flush(); } } flusher;
}
using io::read;
using io::print;
const int INF = 0x3f3f3f3f;
// "梳子"结构体，表示 F_min + F_{min+2} + ... + F_max
struct Comb {
int min_idx, max_idx;
Comb(int l = 0, int r = 0) : min_idx(l), max_idx(r) {}
// set需要一个排序依据，我们按max_idx排序
bool operator<(const Comb &other) const {
return max_idx < other.max_idx;
}
};
std::set<Comb> comb_set;
using Iter = std::set<Comb>::iterator;
long long total_partition_count;
// 更新总答案。在集合中添加或删除梳子p2时，它与前后梳子p1, p3的关系会影响答案
void update_answer(Comb p1, Comb p2, int sign) {
if (p2.max_idx == INF) return;
// 情况1: 梳子p2从F_1或F_2开始
// 贡献就是它自身的项数
if (p2.min_idx <= 2) {
total_partition_count += sign * ((p2.max_idx - p2.min_idx) / 2 + 1);
}
// 情况2: 梳子p2从 > F_2 的地方开始
// 贡献 = 自身项数 + 填补与前一个梳子p1之间空隙产生的项数
else {
int prev_bound = (p1.max_idx == -INF) ? 0 : (p1.min_idx <= 2 ? p1.max_idx : p1.max_idx - 1);
long long comb_size = (p2.max_idx - p2.min_idx) / 2 + 1;
long long gap_fill_count = (p2.min_idx - prev_bound - 3) / 2;
total_partition_count += sign * (comb_size + gap_fill_count);
}
}
void insert_comb(Comb c) {
Iter it = comb_set.insert(c).first;
Iter prev = it, next = it;
--prev; ++next;
update_answer(*prev, *next, -1); // 减去旧的 p1-p3 间隙贡献
update_answer(*prev, *it, 1); // 加上 p1-it 间隙贡献
update_answer(*it, *next, 1); // 加上 it-p3 间隙贡献
}
void erase_comb(Iter it) {
Iter prev = it, next = it;
--prev; ++next;
update_answer(*prev, *it, -1); // 减去 p1-it
update_answer(*it, *next, -1); // 减去 it-p3
update_answer(*prev, *next, 1); // 加上 p1-p3
comb_set.erase(it);
}
// 声明函数，因为它们会相互递归调用
void put(int pos);
void take(int pos);
// 处理在梳子内部添加 F_pos 的情况
// 对应 2*F_k = F_{k+1} + F_{k-2}
void handle_put_inside_comb(Iter it, int pos) {
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
// 原梳子分裂
if (cur_min != pos) insert_comb(Comb(cur_min + 1, pos - 1));
// 递归处理 F_{k+1} 和 F_{k-2}
put(cur_max + 1);
if (cur_min != 1) put(cur_min == 2 ? 1 : cur_min - 2);
}
// 处理在梳子右边添加 F_pos 的情况
// 对应 F_{k} + F_{k+1} = F_{k+2}
void handle_put_right_of_comb(Iter it, int pos) {
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
if (cur_min != cur_max) insert_comb(Comb(cur_min, cur_max - 2));
put(pos + 1);
}
// 处理在梳子间隙添加 F_pos 的情况
void handle_put_in_gap(Iter it, int pos) {
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
if (cur_min <= pos - 1) insert_comb(Comb(cur_min, pos - 1));
put(cur_max + 1);
}
// 添加 F_pos
void put(int pos) {
// 找到第一个 max_idx >= pos-1 的梳子
Iter it = comb_set.lower_bound(Comb(0, pos - 1));
// Case 1: pos 与梳子 it "接触"
if (it->min_idx - 1 <= pos && pos <= it->max_idx + 1) {
if (pos == it->max_idx + 1) { // 接触右边
handle_put_right_of_comb(it, pos);
} else if ((it->max_idx - pos) % 2 == 1) { // 在奇数距离的间隙
handle_put_in_gap(it, pos);
} else { // 在偶数距离的间隙 (即内部)
handle_put_inside_comb(it, pos);
}
}
// Case 2: pos 在梳子之间，可能创造新梳子或与前后合并
else {
Iter next = it;
Iter prev = it;
--prev;
int new_min = pos, new_max = pos;
// 尝试与右边的梳子合并
if (next->min_idx == pos + 2) {
new_max = next->max_idx;
erase_comb(next);
}
// 尝试与左边的梳子合并
if (prev->max_idx == pos - 2) {
new_min = prev->min_idx;
erase_comb(prev);
}
insert_comb(Comb(new_min, new_max));
}
}
// 移除 F_pos
void take(int pos) {
Iter it = comb_set.lower_bound(Comb(0, pos));
// Case 1: pos 就在梳子 it 里面
if (it->min_idx <= pos && pos <= it->max_idx && (pos - it->min_idx) % 2 == 0) {
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
if (cur_min < pos) insert_comb(Comb(cur_min, pos - 2));
if (pos < cur_max) insert_comb(Comb(pos + 2, cur_max));
}
// Case 2: pos 在梳子外面，需要逆向操作
else {
// 这部分是 put 的逆操作，逻辑非常复杂，涉及多种情况的拆解
if (pos < it->min_idx) {
if ((it->min_idx - pos) % 2 == 1) { // TakeT1 logic
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
if (cur_min != cur_max) insert_comb(Comb(cur_min + 2, cur_max));
if (pos <= cur_min - 3) insert_comb(Comb(pos + 2, cur_min - 1));
put(pos == 1 ? 1 : pos - 1);
} else { // TakeT2 logic
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
if (cur_min != cur_max) insert_comb(Comb(cur_min + 2, cur_max));
if (pos <= cur_min - 4) insert_comb(Comb(pos + 3, cur_min - 1));
put(pos + 1);
}
} else { // TakeT3 logic
int cur_min = it->min_idx, cur_max = it->max_idx;
erase_comb(it);
if (pos <= cur_max - 3) insert_comb(Comb(pos + 3, cur_max));
insert_comb(Comb(cur_min + 1, pos));
if (cur_min != 1) put(cur_min == 2 ? 1 : cur_min - 2);
}
}
}
// --- 黑魔法区: a * F_b -> sum of +/- F_k ---
// 这个函数用于将 a * F_b 分解成一系列 +/- F_k 的和
// 它基于斐波那契数系的性质，非常复杂
int _coeff[810], *coeff = _coeff + 405;
int _temp_coeff[810], *temp_coeff = _temp_coeff + 405;
int mod_pos[95], mod_sign[95], mod_count;
void get_modifications(int a, int b) {
if (!a) { mod_count = 0; return; }
int sign = a < 0 ? -1 : 1;
a = std::abs(a);
int l = 0, r = 0;
coeff[0] = 1;
for (int j = 30 - __builtin_clz(a); j >= 0; --j) {
int nl = l, nr = r;
for (int i = l; i <= r; ++i) if (coeff[i]) {
int k = i; while (coeff[k + 2]) k += 2;
if (i == k) {
int k2 = i; while (coeff[k2 + 3]) k2 += 3;
for (int p = k2 + 1; p >= i; p -= 2) ++temp_coeff[p];
if ((k2 - i) / 3 % 2 == 0) ++temp_coeff[i - 2];
nr = std::max(nr, k2 + 1); nl = std::min(nl, i - 2);
i = k2;
} else {
++temp_coeff[k + 2], nr = std::max(nr, k + 2);
++temp_coeff[i - 2], nl = std::min(nl, i - 2);
for (int p = i + 2; p <= k - 2; p += 2) ++temp_coeff[p];
i = k;
}
}
l = nl, r = nr;
for (int i = l; i <= r; ++i) coeff[i] = temp_coeff[i], temp_coeff[i] = 0;
while (l <=r && !coeff[l]) ++l; if(l>r) l=r=0;
while (l <=r && !coeff[r]) --r; if(l>r) l=r=0;
for (int i = l; i <= r; ++i) if (coeff[i] == 2) ++coeff[i + 1], ++coeff[i - 2], coeff[i] = 0;
nl = l, nr = r;
for (int i = r; i >= l; --i) if (coeff[i] && coeff[i + 1]) {
int k = i + 1; while (coeff[k + 2]) k += 2;
++coeff[k + 1];
for (int p = k; p >= i + 1; p -= 2) coeff[p] = 0;
coeff[i] = 0;
nr = std::max(nr, k + 1);
}
l = nl, r = nr;
while (l <=r && !coeff[l]) ++l; if(l>r) l=r=0;
while (l <=r && !coeff[r]) --r; if(l>r) l=r=0;
if ((a >> j) & 1) {
nl = l, nr = r;
if (coeff[0]) {
int k = 0; while (coeff[k - 2]) k -= 2;
for (int p = 1; p >= k; --p) coeff[p] ^= 1;
coeff[k - 2] = 1;
nr = std::max(nr, 1); nl = std::min(nl, k - 2);
} else coeff[0] = 1;
l = nl, r = nr;
for (int i = r; i >= l; --i) if (coeff[i] && coeff[i + 1]) {
int k = i + 1; while (coeff[k + 2]) k += 2;
++coeff[k + 1];
for (int p = k; p >= i + 1; p -= 2) coeff[p] = 0;
coeff[i] = 0;
nr = std::max(nr, k + 1);
}
l = nl, r = nr;
while (l <=r && !coeff[l]) ++l; if(l>r) l=r=0;
while (l <=r && !coeff[r]) --r; if(l>r) l=r=0;
}
}
mod_count = 0;
for (int i = l; i <= r; ++i) if (coeff[i]) {
mod_count++;
mod_pos[mod_count] = b + i;
mod_sign[mod_count] = sign;
}
for (int i = l; i <= r; ++i) coeff[i] = 0;
}
int final_mod_pos[95], final_mod_sign[95], final_mod_count;
// F_{-k} = (-1)^{k-1} F_k
void normalize_modification(int pos, int sign) {
if (pos == -1) return;
if (pos == 0 || pos == -2) pos = 1; // F_0 -> F_1, F_{-2} -> F_1
if (pos < -2) {
sign *= (pos & 1) ? -1 : 1;
pos = -2 - pos;
}
final_mod_count++;
final_mod_pos[final_mod_count] = pos;
final_mod_sign[final_mod_count] = sign;
}
void solve() {
total_partition_count = 0;
comb_set.clear();
comb_set.insert(Comb(INF, INF));
comb_set.insert(Comb(-INF, -INF));
int Q;
read(Q);
while (Q--) {
int a, b;
read(a), read(b);
get_modifications(a, b);
final_mod_count = 0;
for (int i = 1; i <= mod_count; ++i) {
normalize_modification(mod_pos[i], mod_sign[i]);
}
for (int i = 1; i <= final_mod_count; ++i) {
if (final_mod_sign[i] == 1) put(final_mod_pos[i]);
}
for (int i = 1; i <= final_mod_count; ++i) {
if (final_mod_sign[i] == -1) take(final_mod_pos[i]);
}
print(total_partition_count);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int T;
read(T);
while (T--) {
solve();
}
return 0;
}复杂度分析
时间复杂度: 每次操作 x += a * F_b，我们需要先调用 get_modifications(a, b)。这个函数的复杂度与 a 的二进制位数有关，大约是 乘以一些与斐波那契数系相关的多项式因子（但实际上很快）。它会生成 个 的操作。对于每一个 ，我们需要在 std::set 中进行查找和修改。set 的大小与 的对数成正比，因为斐波那契数是指数增长的。所以每次 set 操作是 。因此，单次查询的总时间复杂度可以估算为 。对于 次查询，总复杂度是 。
空间复杂度: 我们用 std::set 来存储梳子。梳子的数量级是 。get_modifications 函数内部使用了一些辅助数组，但大小是固定的。所以空间复杂度是 。
知识点总结
这道题是数据结构、数论和算法设计思想的完美结合，喵~
- 斐波那契数系的表示: 核心思想是找到一种能唯一表示任意整数的、基于斐波那契数的结构。本题解中的“梳子表示法”就是这样一种强大的工具。
- 数据结构维护:
std::set在这里大放异彩。它能自动维护梳子的有序性，并允许我们高效地（对数时间）进行查找、插入和删除，这对于实现复杂的put和take操作至关重要。 - 摊还分析与递归更新:
put和take中的递归调用看起来可能很吓人，但实际上，每次操作（如合并或分裂）都会使表示更加“规范化”，总的计算量是可控的。 - 问题转化: 成功地将一个对大数的操作问题，转化为了对一个紧凑数据结构（梳子集合）的维护问题，是解题的关键。
- 化繁为简: 面对像
a * F_b这样复杂的项，通过get_modifications函数将其分解为一系列更简单的基元操作 ，这是一种非常重要的算法思想。
希望这篇题解能帮到你，主人！如果还有不懂的地方，随时可以再来问这只我哦，喵~