OR10. 上高楼
描述
现在有一栋高楼，但是电梯却出了故障，无奈的你只能走楼梯上楼，根据你的腿长，你一次能走1级或2级楼梯，已知你要走n级楼梯才能走到你的目的楼层，请计算你走到目的楼层的方案数，由于楼很高，所以n的范围为int范围内的正整数。
给定楼梯总数n，请返回方案数。为了防止溢出，请返回结果Mod 1000000007的值。
3
返回：3
C++ 解法, 执行用时: 1ms, 内存消耗: 500KB, 提交时间: 2017-09-19
typedef long long ll;
const int mod=1000000007;
typedef vector<ll> vec;
typedef vector<vec> mat;
class GoUpstairs {
public:
mat mul(mat &a,mat &b)//
{
mat c(a.size(),vec(b[0].size()));
for(int i=0; i<2; i++)
{
for(int j=0; j<2; j++)
{
for(int k=0; k<2; k++)
{
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
}
}
return c;
}
mat pow(mat a,ll n)
{
mat res(a.size(),vec(a.size()));
for(int i=0; i<a.size(); i++)
res[i][i]=1;//单位矩阵；
while(n)
{
if(n&1) res=mul(res,a);
a=mul(a,a);
n/=2;
}
return res;
}
ll countWays(ll n) {
mat a(2,vec(2));
a[0][0]=1;
a[0][1]=1;
a[1][0]=1;
a[1][1]=0;
a=pow(a,n);
return a[0][0];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 432KB, 提交时间: 2022-06-16
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];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 476KB, 提交时间: 2020-10-31
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];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 480KB, 提交时间: 2020-10-31
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];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 484KB, 提交时间: 2020-11-01
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];
}
};