0%

跳台阶

发表于

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

可知设a[n]为n级台阶的跳法，则a[n+1] = a[n] + a[n-1]。

令

A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}

有

[a[n+1]a[n]00]=[a[n]a[n−1]00]×A=[2100]×An−1\begin{bmatrix} a[n+1] & a[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} a[n] & a[n-1] \\ 0 & 0 \\ \end{bmatrix} \times A = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times A ^{n-1}

考虑快速幂，有

An=(A⌊n2⌋)2×An%2A^n = (A^{\lfloor \frac{n}{2} \rfloor})^2 \times A^{n\%2}

故

[a[n+1]a[n]00]=[2100]×(A⌊n−12⌋)2×A(n−1)%2\begin{bmatrix} a[n+1] & a[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times (A^{\lfloor \frac{n-1}{2} \rfloor})^2 \times A^{(n-1)\%2} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int base[4] = {1, 1, 1, 0}, a_n[4] = {1, 1, 1, 0};
    void times(int a[4], int b[4])
    {
        int r[4] = {
            a[0] * b[0] + a[1] * b[2],
            a[0] * b[1] + a[1] * b[3],
            a[2] * b[0] + a[3] * b[2],
            a[2] * b[1] + a[3] * b[3]};
        a[0] = r[0];
        a[1] = r[1];
        a[2] = r[2];
        a[3] = r[3];
    }
    void cal_a(int n)
    {
        if (n > 1)
        {
            n -= 2;
            while (n)
            {
                if (n & 1)
                {
                    times(a_n, base);
                }
                times(base, base);
                n >>= 1;
            }
        }
    }
    int jumpFloor(int n)
    {
        if (n == 1)
        {
            return 1;
        }
        if (n == 2)
        {
            return 2;
        }
        else
        {
            int m[4] = {2, 1, 0, 0};
            cal_a(n - 1);
            times(m, a_n);
            return m[0];
        }
    }
};