# L13-Ladder
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/13-fibonacci_numbers/ladder/
## Key
1. 題目有點難理解，A陣列中每個元素都是一個梯子，每個梯子每次只能爬1-2格，所以剛好爬到頂端的方法數跟費氏數列有關(上題)，這邊用一個陣列/雜湊表紀錄每個長度梯子所能有的方法數

2. 費氏數列就會對應到A[i]的數目，再依題目求x mod 2^B[i]值，它這是為了減少記憶體使用，所以不是紀錄方法數，而是方法數的餘數，比起直接用%算餘數(運行時間比較久)，這邊2的次方有個特殊算法，用位元運算

3. x mod 2^B[i] = x & 2^B[i]-1意義在於看倒數幾個位元是否為1
ex. x mod 4 = x & 3 -> 看倒數兩個位元

## Reference
[某個留言提到mod算法](https://stackoverflow.com/questions/4003232/how-to-code-a-modulo-operator-in-c-c-obj-c-that-handles-negative-numbers)

[and 1原理](https://stackoverflow.com/questions/38922606/what-is-x-1-and-x-1)

## Solution

#include<math.h>
const int M = (1 << 30) - 1;

vector<int> solution(vector<int> &A, vector<int> &B) {
    // write your code in C++14 (g++ 6.2.0)
    int m = 0;
    for (int i = 0; i < (int)A.size(); ++i) {
        m = max(m, A[i]);
    }
    
    vector<int> fb;
    fb.resize(m + 1);
    fb[0] = fb[1] = 1;
    int size = A.size();
    for (int i = 2; i <= m; i++) {
        fb[i] = (fb[i - 1] + fb[i - 2]) & M;
    }
    vector<int> res;
    for (int i = 0; i < size; i++) {
        res.push_back(fb[A[i]] & ((1 << B[i]) - 1));
    }
    
    return res;
}