[已解决]啸策逝1

KeyError · 发表于 2023-11-12 17:57:34

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 KeyError 于 2023-11-27 17:32 编辑

背景
张三（对就是那个法外狂徒）发了酒疯，要你帮他算广义费波纳基数列。
因为他很狂所以你要在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 · 发表于 2023-11-13 20:04:03

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

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

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小 · 发表于 2023-11-12 17:58:42

这个问题可以用递归或者循环来解决。以下是一个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取模后输出。

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

print("答案")

复制代码

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

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

登录/注册后可看大图

liuhongrun2022 · 发表于 2023-11-12 20:05:18

### 题目

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

题目背景：

张三（对就是那个法外狂徒）发了酒疯，要你帮他算广义费波纳基数列。因为他很狂所以你要在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 · 发表于 2023-11-13 17:58:21

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

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

KeyError · 发表于 2023-11-13 17:59:30

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

食不食油饼

KeyError · 发表于 2023-11-13 18:01:36

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

牛批

KeyError · 发表于 2023-11-13 18:06:37

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

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

琅琊王朝 · 发表于 2023-11-14 20:44:02

/kill 张三
/kill KeyErrow

复制代码

或者

print('答案')

复制代码

zhangjinxuan · 发表于 2023-12-19 15:09:24

这个最佳答案由 zhangjinxuan 给出，感谢 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) 的定义不太明确，我就懒得管这些了

账号		自动登录	找回密码
密码			立即注册

[已解决]啸策逝1

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

浏览过的版块