Climbing Stairs
Total Accepted: 18939 Total
Submissions: 56516My Submissions
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
a[n]为上n格的方法数（从1开始计数）
a[0]=1(还没上）,a[1]=1,a[n]=a[n-1]+a[n-2].
X0 X1 * ( 0 1 )^n = Xn Xn+1
0 0 ( 1 1 ) 0 0
class Solution {
public:
void mul(int (*src)[2],int (*m)[2]){
int a=src[0][0],b=src[0][1],c=src[1][0],d=src[1][1];
int e=m[0][0],f=m[0][1],g=m[1][0],h=m[1][1];///@error: fault m[] as src[]
src[0][0]=a*e+b*g;
src[0][1]=a*f+b*h;
src[1][0]=c*e+d*g;
src[1][1]=c*f+d*h;
}
int cal(int (*a)[2],int (*base)[2],int n){
while(n>0){
if(n&1) mul(a,base);//a*=base
n>>=1;
mul(base,base);
}
return a[0][0];
}
int climbStairs(int n) {//a[n]=a[n-1]+a[n-2]
int a[2][2]={{1,1},{0,0}};//c[0] c[1]
int base[2][2]={{0,1},{1,1}};
return cal(a,base,n);
}
};