啸策逝1
本帖最后由 KeyError 于 2023-11-27 17:32 编辑背景
张三（对就是那个法外狂徒）发了酒疯，要你帮他算广义费波纳基数列。
因为他很狂所以你要在2秒之内算出来，不然他就会 你。
描述
张三会给你一个小于232的正整数n，请你算出数列的第n项 mod 232。
（广义费波纳基数列是指f(x)=p*f(x-2)+q*f(x-1)的数列）
输入格式
n p q
输出格式
答案
数据范围
0<n<232
0<p,q<10
注:
当p=q=1时:
f0 = 1
f1 = 1
f2 = 2
f3 = 3
f4 = 5
f5 = 8
...
已更改mod 凯布尔第二定理:
对任意p,q, 都有:
f(2a) = f(a-1)2+f(a)2 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)
这个问题可以用递归或者循环来解决。以下是一个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("答案")
{:10_256:} 陶远航 发表于 2023-11-12 18:35
{:10_256:}
https://t1.wodetu.cn/2023/11/12/8c3c05f49c523bcc1a2d44b810a6259d.png ### 题目
题目名：广义费波纳基数列
题目背景：
张三（对就是那个法外狂徒）发了酒疯，要你帮他算广义费波纳基数列。因为他很狂所以你要在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秒内求解的要求。 isdkz 发表于 2023-11-12 17:57
#1输入:
2147483647 3 3
#1输出:
超时 陶远航 发表于 2023-11-12 18:35
食不食油饼{:10_277:} liuhongrun2022 发表于 2023-11-12 19:59
牛批{:10_277:} Mike_python小 发表于 2023-11-12 17:58
这个问题可以用递归或者循环来解决。以下是一个C++的递归解法：
测试点#1:
2147483647 3 3
#1输出：
超时 /kill 张三
/kill KeyErrow
或者
print('答案')
{:10_256:} 哈哈，矩阵快速幂板子题,改一下矩阵的数字就行了。代码：
#include <bits/stdc++.h>
using namespace std;
const long long p = 1ll << 32;
struct Info {
long long data;
int n, m;
void init() {
data = data = data = data = 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 += data * b.data % p,
res.data %= 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 = 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 = x;
a.data = y;
a.data = 1;
a.data = 0;
Info f0;
f0.init();
f0.n = 1;
f0.m = 2;
f0.data = 1;
f0.data = 1;
return (qpow(a, n) * f0).data;
}
int main() {
long long n;
scanf("%lld%lld%lld", &n ,&x, &y);
printf("%lld\n",fib(n));
}
f(0), f(1),f(2) 的定义不太明确，我就懒得管这些了
页:
[1]