Criska

矩阵乘法+快速幂

• 分类: 矩阵乘法 • 标签: 矩阵乘法

*MDZZ…………难写死了QAQ………………
不过矩阵乘法挺好理解的，总的来说，就是省略了中间递推的过程，直接通过快速幂得到最终的答案，时间复杂度为O（logn），具体原理如下：


【例题】小M 玩数列

【问题描述】
小W 发现了一个神奇的数列：
f(n) = f(n − 1) + f(n − 2) ｛􀀂n≥ 3, n(1) = 1, n(2) = 1｝，这就是著名的 Fibonacci
Sequence = =!。
众所周知，小M 的数学超级超级好，于是给小W 出了一道题：
给小W 两个数X,Y,其中 X ≤ Y≤ 2^31−1。
小W 任务就是求出 Fibonacci 数列第X~Y 项的和除以10000 的余数。
然而小W 是数学战五渣，于是只能把这个任务交给机智的你啦。
【输入格式】
第一行一个整数T，表示数据组数。
接下来T 行，每行两个数X,Y，意义如题所述。
【输出格式】
T 行，每行是一个询问的答案。
【输入输出样例】
fibonacci.in
2
1 5
127 255

fibonacci.out
12
5976
【数据规模】
对于80%的数据：T=1，Y<=10^6
对于100%的数据：T<=1000,Y<=2^31-1

  • 这道题就是很裸的矩阵乘法啦，不过唯一要注意的是，对于斐波那契数列，S(N)=F(N+2)-1，这样就会快很多了。

附上代码：

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
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
long long x,y,st,ed,sum;
long long X[3][3],A[3][3]={{0,0,0},{0,1,1},{0,1,0}},
                  N[3][3]={{0,0,0},{0,1,1},{0,1,0}};
inline int cheng(int x)
{
	for(int i=0;i<=2;++i)
		for(int j=0;j<=2;++j)	
			X[i][j]=0;//不要忘记清零和初始化数组 
	if(x==0)
	{
		for(int i=1;i<=2;++i)
			for(int j=1;j<=2;++j)
				for(int k=1;k<=2;++k)
					X[i][j]=(X[i][j]+A[i][k]*N[k][j])%10000;
		for(int i=0;i<=2;++i)
			for(int j=0;j<=2;++j)	
				N[i][j]=X[i][j];		
	}		
	else
	{
		for(int i=1;i<=2;++i)
			for(int j=1;j<=2;++j)
				for(int k=1;k<=2;++k)
					X[i][j]=(X[i][j]+N[i][k]*N[k][j])%10000;
		for(int i=0;i<=2;++i)
			for(int j=0;j<=2;++j)	
				N[i][j]=X[i][j];	
	}
}
inline void qingkong()
{
	X[1][1]=X[1][2]=X[2][1]=X[2][2]=A[2][2]=N[2][2]=0;
	A[1][1]=N[1][1]=A[1][2]=N[1][2]=A[2][1]=N[2][1]=1;
}
inline void mi(long long n)
{
	if(n==1) return ;
	mi(n/2);
	cheng(1);
	if(n%2) cheng(0);	
}
int main()
{
	freopen("fibonacci.in","r",stdin);
	freopen("fibonacci.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=t;++i)
	{
		scanf("%lld%lld",&x,&y);//斐波那契数列中，S(N)=F(N+2)-1
		if(x==1) st=0;
		else
		{
			mi(x-1);
			st=(N[1][1]+N[2][1]-1)%10000;			
		}
		qingkong(); //数组初始化 
		mi(y);
		ed=(N[1][1]+N[2][1]-1)%10000;
		qingkong();//数组初始化 
		sum=(ed-st)%10000+10000;
		printf("%lld\n",sum%10000);		
	}
	return 0;
}