现在有一栋高楼,但是电梯却出了故障,无奈的你只能走楼梯上楼,根据你的腿长,你一次能走1级或2级楼梯,已知你要走n级楼梯才能走到你的目的楼层,请计算你走到目的楼层的方案数,由于楼很高,所以n的范围为int范围内的正整数。
给定楼梯总数n,请返回方案数。为了防止溢出,请返回结果Mod 1000000007的值。
测试样例:
3
返回:3
class GoUpstairs { public: void mul(long a[2][2], long b[2][2]) { long t[2][2],mod=1e9+7; t[0][0] = (a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod; t[0][1] = (a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod; t[1][0] = (a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod; t[1][1] = (a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod; memcpy(a, t, sizeof(long)*4); } int countWays(int n) { long m[2][2] = {1,1,1,0}, e[2][2] = {1,0,0,1}; while(n>1) { if(n&1) mul(e,m); mul(m,m); n>>=1; } mul(m,e); return m[0][0]; } };
# -*- coding:utf-8 -*- def MatrixMul(a, b): r = [[0, 0], [0, 0]] r[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % 1000000007 r[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % 1000000007 r[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % 1000000007 r[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % 1000000007 return r def QuickMatrixPower(A, n): if n == 1: return A Temp = QuickMatrixPower(A, n / 2) if n % 2 == 1: return MatrixMul(MatrixMul(Temp, Temp), A) return MatrixMul(Temp, Temp) class GoUpstairs: def countWays(self, n): if n <= 3: return [1, 2, 3][n - 1] else: return MatrixMul(QuickMatrixPower([[1, 1],[1, 0]], n - 1),[[1, 2],[1, 1]])[0][0] % 1000000007
class GoUpstairs
class GoUpstairs { void mul(long a[4],long b[4]){ long t[4],mod=1e9+7; t[0]=(a[0]*b[0]+a[1]*b[2])%mod; t[1]=(a[0]*b[1]+a[1]*b[3])%mod; t[2]=(a[2]*b[0]+a[3]*b[2])%mod; t[3]=(a[2]*b[1]+a[3]*b[3])%mod; memcpy(a,t,sizeof(long)*4); } public: int countWays(int n) { // write code here long m[4]={1,1,1,0},e[4]={1,0,0,1}; for(;n>1;n>>=1){ if (n&1) mul(e,m); mul(m,m); } mul(m,e); return m[0]; } };
import java.util.*; //就是用矩阵快速幂法求裴波那契数列 public class GoUpstairs { public int countWays(int n) { long a[][]={{1,1},{1,0}}; long res[][]={{1,0},{0,1}}; while(n>0) { if((n&1)==1) res=digui(a,res); a=digui(a,a); n>>=1; } return (int)res[0][0]; } public long [][] digui(long a[][],long res[][]) { long res1[][]=new long[2][2]; for(int i=0;i<2;i++) for(int j=0;j<2;j++) res1[i][j]=(res[i][0]*a[0][j]+res[i][1]*a[1][j])%1000000007; for(int i=0;i<2;i++) for(int j=0;j<2;j++) res[i][j]=res1[i][j]; return res; } }
# -*- coding:utf-8 -*- #思路大致是:由递推公式得到简化后的矩阵运算式: #( f(n),f(n-1) ) = ( f(2), f(1) ) * matrix(n-2) #其中,int[][] matirx = { {1,1},{1,0}}。 #时间复杂度的降低,在于降低求矩阵的n次方的时间复杂度。 def MatrixMul(a, b):#矩阵相乘 r = [[0, 0], [0, 0]] r[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % 1000000007 r[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % 1000000007 r[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % 1000000007 r[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % 1000000007 return r def QuickMatrixPower(A, n):#快速求矩阵的N次方 if n == 1: return A Temp = QuickMatrixPower(A, n / 2) if n % 2 == 1: return MatrixMul(MatrixMul(Temp, Temp), A) return MatrixMul(Temp, Temp) class GoUpstairs: def countWays(self, n): if n <= 3: return [1, 2, 3][n - 1] else: return MatrixMul(QuickMatrixPower([[1, 1],[1, 0]], n - 1),[[1, 2],[1, 1]])[0][0] % 100000000
class GoUpstairs { public: int fact(int n,int a,int b){ int t=1; int i,temp; if(a<b){ temp=a; a=b; b=temp; } if(n==a) return 1; for(i=n;i>a;i--){ t=t*i; if(b>1&&t%b==0){ t=t/b; b--; } } while(b>1){ t=t/b; b--; } return t; } int countWays(int n) { // write code here int i; int m,sum=0; for(i=0;i<=n/2;i++){ m=fact(n-i,i,n-i-i); sum+=m; } return sum%1000000007; } };
void mul(long x[], long y[], long mod) { long a0[4],a1[4]; for (int i = 0;i < 4;i++) { a0[i] = x[i]; a1[i] = y[i]; } x[0] = (a0[0] * a1[0] + a0[1] * a1[2]) % mod; x[1] = (a0[0] * a1[1] + a0[1] * a1[3]) % mod; x[2] = (a0[2] * a1[0] + a0[3] * a1[2]) % mod; x[3] = (a0[2] * a1[1] + a0[3] * a1[3]) % mod; } int countWays(int n) { // write code here long mod = 1000000007; if (n<0) return 0; if (n == 1 || n == 2) return n; long x[4] = { 1,0,0,1 }, a1[4] = { 1,1,1,0 }; for (;n != 0;n >>= 1) { if (n & 1 != 0) { mul(x, a1, mod); } mul(a1, a1, mod); } long result = x[0] % mod; return result; }
import java.util.*; public class GoUpstairs { public int countWays(int n) { long[][] res=new long[][]{{1},{1}}; long[][] base=new long[][]{{1,1},{1,0}}; while(n>0){ if((n&1)>0){ res=multiply(base,res); } base=multiply(base,base); n=n>>1; } return (int) res[1][0]%1000000007; } public long[][] multiply(long[][] a,long[][] b){ int L1=a.length; int L2=a[0].length; int L3=b[0].length; long[][] res=new long[L1][L3]; for(int i=0;i<L1;i++) for(int j=0;j<L3;j++) for(int k=0;k<L2;k++) res[i][j]+=a[i][k]*b[k][j]%1000000007; return res; } }
http://www.nowcoder.com/discuss/1820
思路大致是:由递推公式得到简化后的矩阵运算式:
( f(n),f(n-1) ) = ( f(2), f(1) ) * matrix(n-2)
其中,int[][] matirx = { {1,1},{1,0}}。
时间复杂度的降低,在于降低求矩阵的n次方的时间复杂度。
求一个整数m的n次方的时候,我们可以先求出n的二进制表达,具体求解的时候就变成了,二进制上为1的各位的m的相应次方的乘积。
比如,程云老师的例子中,提到:
假设⼀个整数是10,如何最快的求解10的75次⽅。
1, 75的⼆进制形式为1001011。
2, 10的75次⽅=(10^64) * (10^8) * (10^2) * (10^1)。
由此,矩阵的n次方也是如此。
有了上面的思路,不难写出下面的代码
最后注意:
有不足的地方,希望大家批评指正!