/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Matrix
{
   public int[][]muilmatrix(int[][]m1,int[][]m2){
	   int res[][]=new int[m1.length][m2[0].length]; 
	   for(int i=0;i<m2[0].length;i++){
		   for(int j=0;j<m1.length;j++){
			   for(int k=0;k<m2.length ;k++){
				   res[i][j]+=(m1[i][k]*m2[k][j]);
 
			   }
		   }
	   }
 
	System.out.println("m1-------------");
	for (int i = 0; i < m1.length; i++)
	{
	for (int j = 0; j < m1[i].length; j++)
	{
		System.out.print(m1[i][j] + "  ");
	}
	System.out.println();
	}
 
	System.out.println("m2-------------");
	for (int i = 0; i < m2.length; i++)
	{
	for (int j = 0; j < m2[i].length; j++)
	{
		System.out.print(m2[i][j] + "  ");
	}
	System.out.println();
	}
 
	System.out.println("---------------");
	for (int i = 0; i < res.length; i++)
	{
	for (int j = 0; j < res[i].length; j++)
	{
		System.out.print(res[i][j] + "  ");
	}
	System.out.println();
	}
 
	   return res;
   }
   //计算p次方
   public int[][] matrixPower(int [][]m1,int p){
	   int res[][]=new int[m1.length][m1[0].length];
	   for(int i=0;i<m1.length;i++){
		   res[i][i]=1;
	   }
	   int [][]temp=m1;
	   for(;p!=0;p>>=1){
		   if((p&1)!=0){
			   res=muilmatrix(res,temp);
		   }
		   temp=muilmatrix(temp,temp);
		}
 
	   return res;
   }
   public int   Fibonacci(int n){
	   if(n<1)
		   return 0;
	   if(n==1||n==2)
		   return 1;
	   int base[][]={{1,1},{1,0}};
	   int res[][]=matrixPower(base,n-2);
	   return res[0][0]+res[1][0];     //这里为什么是这样，
   }
   public static void main(String args[]){
	   Matrix matrix=new Matrix();
	   int a[][]={{1,1},{1,0}};
	  int b[][]= matrix.matrixPower(a, 2);
	  int c=9;
	  System.out.println(matrix.Fibonacci(c));
	  //输出
 
   }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgTWF0cml4CnsKICAgcHVibGljIGludFtdW11tdWlsbWF0cml4KGludFtdW11tMSxpbnRbXVtdbTIpewoJICAgaW50IHJlc1tdW109bmV3IGludFttMS5sZW5ndGhdW20yWzBdLmxlbmd0aF07IAoJICAgZm9yKGludCBpPTA7aTxtMlswXS5sZW5ndGg7aSsrKXsKCQkgICBmb3IoaW50IGo9MDtqPG0xLmxlbmd0aDtqKyspewoJCQkgICBmb3IoaW50IGs9MDtrPG0yLmxlbmd0aCA7aysrKXsKCQkJCSAgIHJlc1tpXVtqXSs9KG0xW2ldW2tdKm0yW2tdW2pdKTsKCQkJCSAgIAoJCQkgICB9CgkJICAgfQoJICAgfQoJCglTeXN0ZW0ub3V0LnByaW50bG4oIm0xLS0tLS0tLS0tLS0tLSIpOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtMS5sZW5ndGg7IGkrKykKCXsKCWZvciAoaW50IGogPSAwOyBqIDwgbTFbaV0ubGVuZ3RoOyBqKyspCgl7CgkJU3lzdGVtLm91dC5wcmludChtMVtpXVtqXSArICIgICIpOwoJfQoJU3lzdGVtLm91dC5wcmludGxuKCk7Cgl9CgkKCVN5c3RlbS5vdXQucHJpbnRsbigibTItLS0tLS0tLS0tLS0tIik7Cglmb3IgKGludCBpID0gMDsgaSA8IG0yLmxlbmd0aDsgaSsrKQoJewoJZm9yIChpbnQgaiA9IDA7IGogPCBtMltpXS5sZW5ndGg7IGorKykKCXsKCQlTeXN0ZW0ub3V0LnByaW50KG0yW2ldW2pdICsgIiAgIik7Cgl9CglTeXN0ZW0ub3V0LnByaW50bG4oKTsKCX0KCQoJU3lzdGVtLm91dC5wcmludGxuKCItLS0tLS0tLS0tLS0tLS0iKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgcmVzLmxlbmd0aDsgaSsrKQoJewoJZm9yIChpbnQgaiA9IDA7IGogPCByZXNbaV0ubGVuZ3RoOyBqKyspCgl7CgkJU3lzdGVtLm91dC5wcmludChyZXNbaV1bal0gKyAiICAiKTsKCX0KCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJfQoJICAgCgkgICByZXR1cm4gcmVzOwogICB9CiAgIC8v6K6h566XcOasoeaWuQogICBwdWJsaWMgaW50W11bXSBtYXRyaXhQb3dlcihpbnQgW11bXW0xLGludCBwKXsKCSAgIGludCByZXNbXVtdPW5ldyBpbnRbbTEubGVuZ3RoXVttMVswXS5sZW5ndGhdOwoJICAgZm9yKGludCBpPTA7aTxtMS5sZW5ndGg7aSsrKXsKCQkgICByZXNbaV1baV09MTsKCSAgIH0KCSAgIGludCBbXVtddGVtcD1tMTsKCSAgIGZvcig7cCE9MDtwPj49MSl7CgkJICAgaWYoKHAmMSkhPTApewoJCQkgICByZXM9bXVpbG1hdHJpeChyZXMsdGVtcCk7CgkJICAgfQoJCSAgIHRlbXA9bXVpbG1hdHJpeCh0ZW1wLHRlbXApOwoJCX0KCgkgICByZXR1cm4gcmVzOwogICB9CiAgIHB1YmxpYyBpbnQgICBGaWJvbmFjY2koaW50IG4pewoJICAgaWYobjwxKQoJCSAgIHJldHVybiAwOwoJICAgaWYobj09MXx8bj09MikKCQkgICByZXR1cm4gMTsKCSAgIGludCBiYXNlW11bXT17ezEsMX0sezEsMH19OwoJICAgaW50IHJlc1tdW109bWF0cml4UG93ZXIoYmFzZSxuLTIpOwoJICAgcmV0dXJuIHJlc1swXVswXStyZXNbMV1bMF07ICAgICAvL+i/memHjOS4uuS7gOS5iOaYr+i/meagt++8jAogICB9CiAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBhcmdzW10pewoJICAgTWF0cml4IG1hdHJpeD1uZXcgTWF0cml4KCk7CgkgICBpbnQgYVtdW109e3sxLDF9LHsxLDB9fTsKCSAgaW50IGJbXVtdPSBtYXRyaXgubWF0cml4UG93ZXIoYSwgMik7CgkgIGludCBjPTk7CgkgIFN5c3RlbS5vdXQucHJpbnRsbihtYXRyaXguRmlib25hY2NpKGMpKTsKCSAgLy/ovpPlh7oKCSAgCiAgIH0KfQ==