在亚线性时间内计算类似斐波那契的函数

Question

那么，问题来了：

给定一个数字 n，我需要计算它需要递归地计算该数字的斐波那契的调用量，并仅将给定基数中的最后一位数字输出为小数。输入有 2 个数字，第一个是数字 n，第二个是输出应该位于的基数。输出应该是案例编号、第一个输入、第二个输入和计算结果。当第一个条目等于第二个条目等于 0 时，程序应该退出。例如：

输入：
0 100
1 100
2 100
3 100
10 10
3467 9350
0 0

输出：
案例 1：0 100 1
案例 2：1 100 1
案例 3：2 100 3
案例 4：3 100 5
案例 5：10 10 7
案例六：3467 9350 7631

我在尝试解决这个问题时得出了以下公式。作为 c(n) 基数 b 中调用次数的最后一位，我们有：

c(n) = (c(n-1) + c(n-2) + 1) mod b

问题是 n 可以是 0 到 2^63 - 1 之间的任何值，所以我真的需要代码来提高效率。我尝试过以迭代方式或使用动态编程进行操作，但是，尽管它给了我正确的输出，但它并没有在足够短的时间内给我。这是我的代码：

迭代

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<unsigned long long int> v;
    unsigned long long int x,y,co=0;
    cin >> x >> y;
    while(x||y){
        co++;
        v.push_back(1);
        v.push_back(1);
        for(int i=2;i<=x;i++) v.push_back((v[i-1]+v[i-2]+1)%y);
        cout << "Case " << co << ": " << x << " " << y << " " << v[x] << endl;
        cin >> x >> y;
        v.clear();
    }
    return 0;
}

动态规划

#include <iostream>
#include <vector>

using namespace std;

vector<unsigned long long int> v;

unsigned long long c(int x, int y){
    if(v.size()-1 < x) v.push_back((c(x-1,y) + c(x-2,y) + )%y);
    return v[x];
}

int main(){
    int x,y,co=0;
    cin >> x >> y;
    while(x||y){
        co++;
        v.push_back(1);
        v.push_back(1);
        cout << "Case " << co << ": " << x << " " << y << " " << c(x,y) << endl;
        cin >> x >> y;
        v.clear();
    }
    return 0;
}

x和y分别是n和b，v保存c(n)的值

Answer 1

序列中的每个c都小于b。所以 a c 的值有 b 种可能性。所以一对连续的元素[c_k,c_k+1]可以有b²可能值。所以如果你从头开始计算c₁, c₂, c₃...在序列开始重复之前，您最多需要计算其中的 b² 个；你会得到一个 [c_k, c_k+1] 等于之前的 [c_j, c_j+1].

然后你知道循环的长度，称它为S，你知道c_n = c_{((n-j)mod S)+j} 对所有 n > j。那应该会大大减少你的工作量。

在亚线性时间内计算类似斐波那契的函数

Computing fibonacci like function in sublinear time

c++

algorithm

performance

fibonacci