[已解决]啸策逝1

KeyError

背景
张三（对就是那个法外狂徒）发了酒疯，要你帮他算广义费波纳基数列。
因为他很狂所以你要在2秒之内算出来，不然他就会        你。
描述
张三会给你一个小于2³²的正整数n，请你算出数列的第n项 mod 2³²。
（广义费波纳基数列是指f(x)=p*f(x-2)+q*f(x-1)的数列）
输入格式

n p q

输出格式

答案

数据范围
0<n<2³²
0<p,q<10
注:
当p=q=1时:
f0 = 1
f1 = 1
f2 = 2
f3 = 3
f4 = 5
f5 = 8
...

已更改mod

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2023-12-19 15:09:24

哈哈，矩阵快速幂板子题,改一下矩阵的数字就行了。代码：

#include <bits/stdc++.h>
using namespace std;
const long long p = 1ll << 32;
struct Info {
        long long data[4][4];
        int n, m;
        void init() {
                data[1][1] = data[1][2] = data[2][2] = data[2][1] = 0;
                n = m = 0;
        }
        Info operator * (const Info &b) const {
                Info res;
                memset(res.data, 0, sizeof(res.data));
                res.n = n;
                res.m = b.m;
                for (int i = 1; i <= res.n; i++)
                        for (int j = 1; j <= res.m; j++)
                                for (int k = 1; k <= b.n; k++)
                                        res.data[i][j] += data[i][k] * b.data[k][j] % p,
                                        res.data[i][j] %= p; 
                return res;
        }
};


Info qpow(Info a, long long k) {
        Info res;
        res.init();
        res.n = a.n;
        res.m = a.m;
        for (int i = 1; i <= a.n; ++i) res.data[i][i] = 1;
        while (k) {
                if (k & 1) res = res * a;
                a = a * a;
                k >>= 1;
        }
        return res;
}

Info a;
long long k, x, y;
int n;

long long fib(long long n) {
        Info a;
        a.init();
        a.n = a.m = 2;
        a.data[1][1] = x;
        a.data[1][2] = y;
        a.data[2][1] = 1;
        a.data[2][2] = 0;
        Info f0;
        f0.init();
        f0.n = 1;
        f0.m = 2;
        f0.data[1][1] = 1;
        f0.data[1][2] = 1;
        return (qpow(a, n) * f0).data[2][1];
}

int main() {
        long long n;
        scanf("%lld%lld%lld", &n ,&x, &y);
        printf("%lld\n",fib(n));
} 

f(0), f(1),f(2) 的定义不太明确，我就懒得管这些了

跳转到最佳答案楼层

KeyError

凯布尔第二定理:
对任意p,q, 都有:
f(2a) = f(a-1)²+f(a)²

isdkz

def generalized_fibonacci(n, p, q):
    MOD = 2**64
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, (p * a + q * b) % MOD
        return b

n, p, q = map(int, input().split())
result = generalized_fibonacci(n, p, q)
print(result)

Mike_python小

这个问题可以用递归或者循环来解决。以下是一个C++的递归解法：

#include <iostream>using namespace std;unsigned long long fib(int n, int p, int q) {    if (n == 0) return 0;    if (n == 1) return 1;    unsigned long long a = 0, b = 1, c;    for (int i = 2; i <= n; ++i) {        c = (p * b + q * a) % (1ULL << 64);        a = b;        b = c;    }    return b;}int main() {    int n, p, q;    cin >> n >> p >> q;    cout << fib(n, p, q) << endl;    return 0;}

这段代码通过迭代的方法计算了广义斐波那契数列的第n项，并对264取模后输出。

陶远航

print("答案")

liuhongrun2022

陶远航 发表于 2023-11-12 18:35

                               
登录/注册后可看大图

liuhongrun2022

### 题目

题目名：广义费波纳基数列

题目背景：

张三（对就是那个法外狂徒）发了酒疯，要你帮他算广义费波纳基数列。因为他很狂所以你要在2秒之内算出来，不然他就会你。

题目描述：

张三会给你一个小于232的正整数n，请你算出数列的第n项 mod 264。

（广义费波纳基数列是指f(x)=p*f(x-2)+q*f(x-1)的数列）

输入格式：

n p q

输出格式：

答案

数据范围：

- 0<n<232
- 0<p,q<10

### 解题思路

这是一道涉及到线性代数和数论的题目。我们需要利用矩阵快速幂的方法来求解这个问题。

首先，我们可以将广义费波纳基数列的递推公式表示为矩阵形式：

|f(n)  |   = |p   q| * |f(n-2)||f(n-1)|     |1   0|   |f(n-1)|

然后，我们可以通过矩阵快速幂的方法，快速计算出大量的幂，从而得到f(n)。

为了求解模264的数值，我们需要使用模运算的性质。模运算有一个重要的性质，即(a+b) mod m = (a mod m + b mod m) mod m。我们可以利用这个性质，将矩阵的每一个元素都进行模运算，从而得到模264的结果。

矩阵的快速幂运算可以通过如下步骤实现：

1. 将n转换为二进制形式，例如13转换为1101。
2. 从右至左遍历n的二进制形式的每一位，如果该位为1，则将当前的矩阵乘以结果矩阵。然后，将当前的矩阵自乘。
3. 返回结果矩阵的第一行第一列的元素，即为f(n)。

需要注意的是，这种方法的时间复杂度为O(log n)，可以满足在2秒内求解的要求。

KeyError

isdkz 发表于 2023-11-12 17:57

#1输入:
2147483647 3 3
#1输出:
超时

KeyError

陶远航 发表于 2023-11-12 18:35

食不食油饼

KeyError

liuhongrun2022 发表于 2023-11-12 19:59

牛批

KeyError

Mike_python小 发表于 2023-11-12 17:58
这个问题可以用递归或者循环来解决。以下是一个C++的递归解法：

测试点#1:
2147483647 3 3
#1输出：
超时

琅琊王朝

/kill 张三
/kill KeyErrow

或者

print('答案')

zhangjinxuan

哈哈，矩阵快速幂板子题,改一下矩阵的数字就行了。代码：

#include <bits/stdc++.h>
using namespace std;
const long long p = 1ll << 32;
struct Info {
        long long data[4][4];
        int n, m;
        void init() {
                data[1][1] = data[1][2] = data[2][2] = data[2][1] = 0;
                n = m = 0;
        }
        Info operator * (const Info &b) const {
                Info res;
                memset(res.data, 0, sizeof(res.data));
                res.n = n;
                res.m = b.m;
                for (int i = 1; i <= res.n; i++)
                        for (int j = 1; j <= res.m; j++)
                                for (int k = 1; k <= b.n; k++)
                                        res.data[i][j] += data[i][k] * b.data[k][j] % p,
                                        res.data[i][j] %= p; 
                return res;
        }
};


Info qpow(Info a, long long k) {
        Info res;
        res.init();
        res.n = a.n;
        res.m = a.m;
        for (int i = 1; i <= a.n; ++i) res.data[i][i] = 1;
        while (k) {
                if (k & 1) res = res * a;
                a = a * a;
                k >>= 1;
        }
        return res;
}

Info a;
long long k, x, y;
int n;

long long fib(long long n) {
        Info a;
        a.init();
        a.n = a.m = 2;
        a.data[1][1] = x;
        a.data[1][2] = y;
        a.data[2][1] = 1;
        a.data[2][2] = 0;
        Info f0;
        f0.init();
        f0.n = 1;
        f0.m = 2;
        f0.data[1][1] = 1;
        f0.data[1][2] = 1;
        return (qpow(a, n) * f0).data[2][1];
}

int main() {
        long long n;
        scanf("%lld%lld%lld", &n ,&x, &y);
        printf("%lld\n",fib(n));
} 

f(0), f(1),f(2) 的定义不太明确，我就懒得管这些了