关于斐波那契数列的矩阵乘法

浅谈矩阵乘法在斐波那契上的应用-------------By杜保河【题目背景】定义：01121,(2)nnnfffffn。｛fi｝称为Fibonacci数列.【题目要求】输入n，求nfmodq,其中1≤q≤30000。【样例输入】62【样例输出】1【数据范围】n=2000000000.【算法分析】因为n的范围较大，即使是O(n)的算法也不可能在1s时间内出解。所以可以用矩阵乘法来解决此题。时间效率：O(logn)因为，01101120111fffffff122122301,11fffffff11101,11nnnnnnnfffffff所以0110111nnnffff。要求nf,只需要先求0111n,根据矩阵对应元素相等即可求得nf。求0111n利用矩阵乘法规则即可。求的过程利用快速幂。【参考程序1】typesb=array[1..2,1..2]oflongint;varsum,t,n,m,q,i,j:longint;tot,a:sb;proceduremul(varc:sb;a,b:sb);vari,j,k:longint;beginfillchar(c,sizeof(c),0);fori:=1to2doforj:=1to2dofork:=1to2doc[i,j]:=c[i,j]+a[i,k]*b[k,j]modq;end;beginreadln(n,q);ifq=1thenwriteln(0)elsebegintot[1,1]:=1;tot[1,2]:=0;tot[2,1]:=0;tot[2,2]:=1;//相当于快速幂中tot:=1;a[1,1]:=0;a[1,2]:=1;a[2,1]:=1;a[2,2]:=1;//计算矩阵的n次幂！whilen0dobeginifodd(n)thenmul(tot,tot,a);mul(a,a,a);{fori:=1to2dobeginforj:=1to2dowrite(tot[i,j],'');write('|');forj:=1to2dowrite(a[i,j],'');writeln;end;fori:=1to20dowrite('-');writeln(n);}n:=n1;end;//这是什么？？？快速幂！！！writeln(tot[2,2]);end;end.【参考程序2】vari,j,k,top,t,n,f,m,x,y,p:integer;a,b,c,d:array[1..2,1..2]oflongint;q,s:array[1..1000]ofinteger;beginreadln(x);d[1,1]:=1;d[1,2]:=1;b[1,1]:=0;b[1,2]:=1;i:=2;forj:=1to2dob[i,j]:=1;top:=0;fory:=1toxdobegina:=d;m:=0;readln(n,p);whilemndobegini:=1;forj:=1to2dobegint:=0;fork:=1to2dot:=t+a[i,k]*b[k,j];c[i,j]:=t;end;a:=c;m:=m+1;end;m:=c[1,1];top:=top+1;q[top]:=m;s[top]:=p;end;fori:=1totopdowriteln(q[i]mods[i]);end.【题目拓展】一.矩阵1.定义矩阵就是排成行与列的数的阵列，一个m行n列的矩阵可以用符号形式表示为：111212122212nnmmmnaaaaaaaaaa和行、各列上的数叫作矩阵的元素。例如：123456是一个2行3列矩阵，或称为2×3矩阵。当一个矩阵行数等于列数时，叫作方阵。例如：1234567892.几种特殊的矩阵行矩阵：仅有一行的矩阵。例如：1,0,0列矩阵：仅有一列的矩阵。例如：100单位矩阵：主对角线上的元素皆为1，其他元素均为0的矩阵，记为I。例如：100010001就是单位矩阵。对称矩阵：所有主对角线右上方的元素和主对角线左下方的元素对应相等的矩阵。例如：2656145433.矩阵的运算①矩阵的相等。当两个矩阵的对应元素都相等，则称这两个矩阵相等。例如：37ab表示37ab1112121222axbxCaxbxC表示1112121222axbxcaxbxc②矩阵的加减运算。两个矩阵的行数和列数分别相等时，可以相加、相减。两个矩阵相加减时，结果还是矩阵，它的各个元素等于两个矩阵对应元素相加减所得的值。例如：8314251256496526911127328241556831425414496526170732824112③一个数和矩阵相乘。一个数和矩阵相乘，仍是一个矩阵，只要把该数与矩阵中的每个元素相乘即可。例如：10000*2102032132kkkkkkk④矩阵的乘法运算。第一个矩阵的行数等于第二个矩阵的列数时，这两个矩阵可以相乘。例如：已知1412325,45636AB，则A×B为114412451346172227215422552356222936316432653366273645AB参考程序：vara,b,c:array[0..100,0..100]oflongint;n,m,i,j,k,l:longint;beginreadln(n,m);fori:=1tondoforj:=1tomdoread(a[i,j]);fori:=1tomdoforj:=1tondoread(b[i,j]);fori:=1tondoforj:=1tondofork:=1tomdoc[i,j]:=c[i,j]+a[i,k]*b[k,j];fori:=1tondobeginforj:=1tondowrite(c[i,j],'');writeln;end;end.⑤矩阵的转置。矩阵A的转置就是将矩阵A的行和列进行调换，形成一个新的矩阵，记作A′。例如：'14123,2545636AA⑥逆矩阵。如果一个矩阵乘以矩A，得到一个单位矩阵I，则这个矩阵叫作矩阵A的逆矩阵，表示为1A。例如：设123132,221,3/235/2343BA因为1321231003/235/2221010111343001I，所以1BA。⑦矩阵的初等变换。如果一个矩阵相应地进行以下三种变形：(ⅰ)用一个非零常数乘以矩阵某一行的所有元素；(ⅱ)用一个非零常数乘以矩阵的某一行的所有元素，加到另一行的对应元素上去；(ⅲ)互换两行。则这三种变换叫作矩阵的行的初等变换。一个矩阵经过初等变换后，就变为另一个不同的矩阵。例如：二.快速幂快速幂是用来快速计算a^nmodp的一种方法。如果n是偶数则a^n=a^(n/2)*a^(n/2)如果n是奇数则a^n=a^(n/2)*a^(n/2)*a如果在最后才进行modp可能会溢出，根据之前说的mod运算的性质，我们在递归时可以边做边取模。【代码】//求解ans=a^bmodc;functionksm(a,b:longint;c:longint):longint;vartotal:longint;begintotal:=1;whileb0dobeginifodd(b)thentotal:=(total*a)modc;b:=bshr1;a:=(a*a)modc;end;exit(total);end;0231322371、2行互换132023237