23.11.16

题目：

已知一数列的前两项都为1，从第3项开始，奇数项为前两项之和，偶数项为前两项之差。

那么我们很快可以算出数列的前几项：1 1 2 1 3 2……

现在，请你求数列的第n项。

输入：

第一行为正整数T，表示询问的次数

接下来T行，每行包含一个正整数n表示询问的是第几项（0<n<=1000000000，1<=T<=100000）

输出：

输出T行，每行包含一个整数表示本次询问的结果，然后换行。

由于答案可能很大，所以只需要输出它对1000000007取余之后的结果。

样例输入：

3

1

2

3

样例输出：

1

1

2

解题思路：

注：

不要再计算中进行mod操作，会丢失数据的精度。

例如：

​ 此处mod10:

​ 数据为：A，9，12，X

​ 若计算时mod,12mod10=2

​ 数据为：A，9，2，X

​ x=2-9;

​ 与原本数据12-9不符合。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
const unsigned long long mod = 1000000007;
unsigned long long aaaa(long n){
	unsigned long long b[3]={0,1,1};
	if(n==1||n==2){
		return 1;
	}else{
		for(int i=3;i<=n;i++){
			if(i%2==0){
				b[2]=b[1]-b[2];
				//b[2]=b[2]%mod;
			}else{
				b[1]=b[1]+b[2];
				//b[1]=b[1]%mod;
			}
		}
	}
	if(n%2==0){
		return b[2];
	}else{
		return b[1];
	}
}
int main(){
	int n;
	cin>>n;
	long a[n];
	for(int i =0;i<n;i++){
		cin>>a[i];
	}
	cout<<"分割线"<<endl; 
	for(int i=0;i<n;i++){
		cout<<a[i]<<"===="<<aaaa(a[i])%mod<<endl;
	}
	return 0;
}

运行结果：

image

补：

​ 通过分析可知，本题数列与斐波拉契数列之间有着关系。

​ 关系如下：

​ 对于第n项：

​ 若n为奇数的情况下对应斐波拉契数列的第n+3项

​ 若n为偶数的情况下对应斐波拉契数列的第n/2项

​ 由此可见，可以通过构造斐波拉契数列，来求此题。

矩阵快速幂：

​ 斐波拉契数列:Fn = Fn-1+Fn-2

​ 根据此性质可分析出可用矩阵去求某项

​ 其原理在此不在做过多的赘述；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
//定义函数,求二维矩阵：两矩阵 a, b 的乘积---------矩阵 
vector<vector<unsigned long long>> multiply(vector<vector<unsigned long long>>& a, vector<vector<unsigned long long>>& b) {
        vector<vector<unsigned long long>> c{{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
            	//矩阵乘积对应关系
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % mod;
            }
        }
        return c;
    }
//定义函数,求底数为 a 的矩阵幂次为 n 的结果-----------快速幂 
vector<vector<unsigned long long>> pow(vector<vector<unsigned long long>>& a, unsigned long long n) {
        vector<vector<unsigned long long>> ret{{1, 0}, {0, 1}};
        while (n > 0) {
            if (n & 1) {//若为奇数，需多乘一次
                ret = multiply(ret, a);
            }
            //不管幂次是奇还是偶，整除的结果是一样的如 5/2 和 4/2
            //此处使用位运算在于效率高
            n >>= 1;//要用n=n/2;也不是不可以 
            a = multiply(a, a);
        }
        return ret;
    }

unsigned long long fib(unsigned long long n) {
        if (n < 2) {
            return n;
        }
        vector<vector<unsigned long long>> q{{1, 1}, {1, 0}};
        vector<vector<unsigned long long>> res = pow(q, n - 1);
        return res[0][0];
    }

int main(){
	int T;
	cin>>T;
	while(T--){
		unsigned long long n;
		cin>>n;
		if(n%2==1){
			n+=3;
		}
		n/=2;
		cout<<fib(n)<<endl;
	}
	return 0;
}

续：

​ 同时斐波拉契数列也是有通项公式的，可利用通项公式求某项，这里不过多赘述。

链接：

https://leetcode.cn/problems/fibonacci-number/solutions/545049/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

​