问题分析

题目要求计算将一个自然数 ( n ) 表示为多个大于 1 的斐波那契数的乘积的方法数。斐波那契数列定义为 $( F_0=1, F_1=1, F_n=F_{n-2}+F_{n-1} )$，且乘法顺序不影响方法的唯一性（如 $( 2 \cdot 3 )$ 与 $( 3 \cdot 2 )$ 视为同一种方法）。

核心思路

1. 预生成斐波那契数：由于 $( n \leq 10^{18} )$，先生成所有大于 1 且不超过 $( 10^{18} )$ 的斐波那契数（约 90 个），并按从大到小排序。

2. 递归+记忆化搜索：

   • 对于每个 ( n )，尝试用预生成的斐波那契数作为因子分解 ( n )。
   • 从大到小尝试因子，避免重复计算（例如先试 ( 8 ) 再试 ( 5 )，而非相反，确保每种组合仅被计算一次）。
   • 用记忆化缓存中间结果，减少重复递归。

3. 剪枝优化：若当前斐波那契数小于 ( n ) 且不能整除 ( n )，则更小的斐波那契数也无需尝试（因已按从大到小排序）。

算法步骤

1. 生成斐波那契数列表 $( \text{fibs} )$（>1 且 ≤ $( 10^{18} )$），逆序排列。
2. 定义递归函数 $( \text{count}(n)$)：
   • 若 $( n = 1 )$，返回 1（表示空乘积，即分解完成）。
   • 否则，遍历 $( \text{fibs} )$ 中的每个数 ( f )：
     • 若 ( f ) 能整除 ( n )，则累加 $( \text{count}(n/f) )$（递归计算剩余部分的分解方法）。
     • 若 ( f < n ) 且不能整除 ( n )，直接 break（剪枝）。
3. 对每个测试用例，调用 $( \text{count}(n) )$ 并输出结果。

代码实现（Python）

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

// 存储大于1且不超过1e18的斐波那契数（从大到小排序）
vector<long long> fibs;
// 记忆化缓存，存储已计算过的n的分解方法数
unordered_map<long long, long long> memo;

// 生成斐波那契数并逆序排列
void generate_fibs() {
    long long a = 1, b = 1;
    while (true) {
        long long c = a + b;
        if (c > 1e18) {
            break;
        }
        fibs.push_back(c);
        a = b;
        b = c;
    }
    // 逆序排列，确保从大到小尝试因子
    reverse(fibs.begin(), fibs.end());
}

// 计算n的分解方法数
long long count_ways(long long n) {
    if (n == 1) {
        return 1; // 空乘积，分解完成
    }
    // 检查缓存，避免重复计算
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    long long total = 0;
    for (long long f : fibs) {
        if (f > n) {
            continue; // 因子大于n，跳过
        }
        if (n % f == 0) {
            // 若能整除，累加子问题的解
            total += count_ways(n / f);
        }
        // 剪枝：当前因子小于n且不能整除n，更小的因子无需尝试
        if (f < n && n % f != 0) {
            break;
        }
    }
    // 存入缓存
    memo[n] = total;
    return total;
}

int main() {
    generate_fibs(); // 预生成斐波那契数
    
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << count_ways(n) << endl;
    }
    
    return 0;
}

算法复杂度

• 时间复杂度：$( O(t \cdot k \cdot \log n) )$，其中 ( t ) 是测试用例数，( k ) 是斐波那契数的数量（约 90），$( \log n )$ 是递归深度（每次至少除以 2）。
• 空间复杂度：$( O(\log n)$)，主要为记忆化缓存和递归栈空间。

算法标签

• 递归与记忆化
• 斐波那契数列
• 数论（因子分解）
• 动态规划（计数类）
• 剪枝优化