前言

如何快速求出“兔子数列”的第n(好大一个数)位的值嘞？

1.了解一下快速幂

如何求$n^m$？
1.暴力乘出来（很慢很慢）

1
for(int i=1;i<=m;++i) n*=n;

2.用STL库（不开O2优化会很慢）

1
2
3
#include<cmath>
......
pow(n,m)

3.快速幂（利用倍增思想）

1
2
3
4
5
6
7
int power(int a,int b,int P)
{
    int re=1;
    for(;b;b>>=1,a=a*a%P)
        if(b&1) re=re*a%P;
    return re;
}

P.S. If you want to know what is 倍增, Click Here（来自naivekun的博客）

2.了解一下矩阵

以

斐波那契矩阵求法

左边一个2*2的矩阵（以下称 矩阵1 ），下面一个2*1的矩阵（以下称 矩阵2 ），中间一个2*1的矩阵（以下称 矩阵3 ）。
每当我们需要得到一个新的 矩阵3 时，将已有的 矩阵2 乘上构造矩阵 矩阵1 。
矩阵3 的第n行第m列的数由 矩阵2 的第m列的数分别乘 矩阵1 的第n行的数之后求和得到的（如图，计算方式中的项对应矩阵中的相应颜色的项）

那么，如何用程序实现矩阵呢？（以求斐波那契数列为例）
这就要用到结构体定义了。

定义矩阵

1
2
3
4
struct Mat
{
	long long m[3][3];
};

矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline Mat mat_cheng(Mat x,Mat y)
{
	Mat ans;
	for(int i=1;i<=2;++i)
	for(int j=1;j<=2;++j)
	{
		ans.m[i][j]=0;   //初始化为0
		for(int k=1;k<=2;++k)
		{
			ans.m[i][j]+=(x.m[i][k]*y.m[k][j])%p;  //一定是+=，不是=
			ans.m[i][j]%=p;
		}
	}
	return ans;
}

3. ♪I HAVE A 快速幂，I HAVE A 矩阵乘法♪

♪AH~~~ ，矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
inline Mat power(Mat x,long long y)
{
	Mat ans;
	ans.m[1][1]=1;
	ans.m[1][2]=0;
	ans.m[2][1]=1;
	ans.m[2][2]=0;   //造一个单位矩阵
	for(;y;y>>=1,x=mat_cheng(x,x))
		if(y&1) ans=mat_cheng(x,ans);
	return ans;
}

4.利用矩阵快速幂求斐波那契数列第n项

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
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<iostream>
#define p 10000
using namespace std;
long long n;
struct Mat
{
	long long m[3][3];
};
inline Mat mat_cheng(Mat x,Mat y)
{
	Mat ans;
	for(int i=1;i<=2;++i)
	for(int j=1;j<=2;++j)
	{
		ans.m[i][j]=0;
		for(int k=1;k<=2;++k)
		{
			ans.m[i][j]+=(x.m[i][k]*y.m[k][j])%p;
			ans.m[i][j]%=p;
		}
	}
	return ans;
}
inline Mat power(Mat x,long long y)
{
	Mat ans;
	ans.m[1][1]=1;
	ans.m[1][2]=0;
	ans.m[2][1]=1;
	ans.m[2][2]=0;
	for(;y;y>>=1,x=mat_cheng(x,x))
		if(y&1) ans=mat_cheng(x,ans);
	return ans;
}
Mat s;
int main()
{
	scanf("%lld",&n);
	s.m[1][1]=1;
	s.m[1][2]=1;
	s.m[2][1]=1;
	s.m[2][2]=0;
	if(n==1)
	{
		printf("1");
		return 0;
	} 
	if(n==2)
	{
		printf("1");
		return 0;
	} 
	s=power(s,n-3);
	printf("%lld",(s.m[1][1]+s.m[2][1])%p);
	return 0;
}