[已解决]啸策逝1

KeyError

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

1. n p q

复制代码

输出格式

1. 答案

复制代码

数据范围
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

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const long long p = 1ll << 32;
   
4. struct Info {
   
5.         long long data[4][4];
   
6.         int n, m;
   
7.         void init() {
   
8.                 data[1][1] = data[1][2] = data[2][2] = data[2][1] = 0;
   
9.                 n = m = 0;
   
10.         }
    
11.         Info operator * (const Info &b) const {
    
12.                 Info res;
    
13.                 memset(res.data, 0, sizeof(res.data));
    
14.                 res.n = n;
    
15.                 res.m = b.m;
    
16.                 for (int i = 1; i <= res.n; i++)
    
17.                         for (int j = 1; j <= res.m; j++)
    
18.                                 for (int k = 1; k <= b.n; k++)
    
19.                                         res.data[i][j] += data[i][k] * b.data[k][j] % p,
    
20.                                         res.data[i][j] %= p;
    
21.                 return res;
    
22.         }
    
23. };
    
24. 
    
25. 
    
26. Info qpow(Info a, long long k) {
    
27.         Info res;
    
28.         res.init();
    
29.         res.n = a.n;
    
30.         res.m = a.m;
    
31.         for (int i = 1; i <= a.n; ++i) res.data[i][i] = 1;
    
32.         while (k) {
    
33.                 if (k & 1) res = res * a;
    
34.                 a = a * a;
    
35.                 k >>= 1;
    
36.         }
    
37.         return res;
    
38. }
    
39. 
    
40. Info a;
    
41. long long k, x, y;
    
42. int n;
    
43. 
    
44. long long fib(long long n) {
    
45.         Info a;
    
46.         a.init();
    
47.         a.n = a.m = 2;
    
48.         a.data[1][1] = x;
    
49.         a.data[1][2] = y;
    
50.         a.data[2][1] = 1;
    
51.         a.data[2][2] = 0;
    
52.         Info f0;
    
53.         f0.init();
    
54.         f0.n = 1;
    
55.         f0.m = 2;
    
56.         f0.data[1][1] = 1;
    
57.         f0.data[1][2] = 1;
    
58.         return (qpow(a, n) * f0).data[2][1];
    
59. }
    
60. 
    
61. int main() {
    
62.         long long n;
    
63.         scanf("%lld%lld%lld", &n ,&x, &y);
    
64.         printf("%lld\n",fib(n));
    
65. }
    

复制代码

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

跳转到最佳答案楼层

KeyError

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

isdkz

1. def generalized_fibonacci(n, p, q):
   
2.     MOD = 2**64
   
3.     if n == 0:
   
4.         return 0
   
5.     elif n == 1:
   
6.         return 1
   
7.     else:
   
8.         a, b = 0, 1
   
9.         for _ in range(2, n + 1):
   
10.             a, b = b, (p * a + q * b) % MOD
    
11.         return b
    
12. 
    
13. n, p, q = map(int, input().split())
    
14. result = generalized_fibonacci(n, p, q)
    
15. print(result)
    

复制代码

Mike_python小

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

2. #include <iostream>
3. using namespace std;
5. unsigned long long fib(int n, int p, int q) {
6.     if (n == 0) return 0;
7.     if (n == 1) return 1;
8.     unsigned long long a = 0, b = 1, c;
9.     for (int i = 2; i <= n; ++i) {
10.         c = (p * b + q * a) % (1ULL << 64);
11.         a = b;
12.         b = c;
13.     }
14.     return b;
15. }
17. int main() {
18.     int n, p, q;
19.     cin >> n >> p >> q;
20.     cout << fib(n, p, q) << endl;
21.     return 0;
22. }

复制代码

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

陶远航

1. print("答案")

复制代码

liuhongrun2022

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

                               
登录/注册后可看大图

liuhongrun2022

### 题目

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

题目背景：

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

题目描述：

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

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

输入格式：

1. n p q

复制代码

输出格式：

1. 答案

复制代码

数据范围：

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

### 解题思路

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

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

1. |f(n)  |   = |p   q| * |f(n-2)|
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输出：
超时

琅琊王朝

1. /kill 张三
   
2. /kill KeyErrow

复制代码

或者

1. print('答案')

复制代码

zhangjinxuan

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const long long p = 1ll << 32;
   
4. struct Info {
   
5.         long long data[4][4];
   
6.         int n, m;
   
7.         void init() {
   
8.                 data[1][1] = data[1][2] = data[2][2] = data[2][1] = 0;
   
9.                 n = m = 0;
   
10.         }
    
11.         Info operator * (const Info &b) const {
    
12.                 Info res;
    
13.                 memset(res.data, 0, sizeof(res.data));
    
14.                 res.n = n;
    
15.                 res.m = b.m;
    
16.                 for (int i = 1; i <= res.n; i++)
    
17.                         for (int j = 1; j <= res.m; j++)
    
18.                                 for (int k = 1; k <= b.n; k++)
    
19.                                         res.data[i][j] += data[i][k] * b.data[k][j] % p,
    
20.                                         res.data[i][j] %= p;
    
21.                 return res;
    
22.         }
    
23. };
    
24. 
    
25. 
    
26. Info qpow(Info a, long long k) {
    
27.         Info res;
    
28.         res.init();
    
29.         res.n = a.n;
    
30.         res.m = a.m;
    
31.         for (int i = 1; i <= a.n; ++i) res.data[i][i] = 1;
    
32.         while (k) {
    
33.                 if (k & 1) res = res * a;
    
34.                 a = a * a;
    
35.                 k >>= 1;
    
36.         }
    
37.         return res;
    
38. }
    
39. 
    
40. Info a;
    
41. long long k, x, y;
    
42. int n;
    
43. 
    
44. long long fib(long long n) {
    
45.         Info a;
    
46.         a.init();
    
47.         a.n = a.m = 2;
    
48.         a.data[1][1] = x;
    
49.         a.data[1][2] = y;
    
50.         a.data[2][1] = 1;
    
51.         a.data[2][2] = 0;
    
52.         Info f0;
    
53.         f0.init();
    
54.         f0.n = 1;
    
55.         f0.m = 2;
    
56.         f0.data[1][1] = 1;
    
57.         f0.data[1][2] = 1;
    
58.         return (qpow(a, n) * f0).data[2][1];
    
59. }
    
60. 
    
61. int main() {
    
62.         long long n;
    
63.         scanf("%lld%lld%lld", &n ,&x, &y);
    
64.         printf("%lld\n",fib(n));
    
65. }
    

复制代码

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