题解 | #统计每个月兔子的总数#

HJ37 统计每个月兔子的总数

1.每什么难度，先将前6个月写出来，发现规律是斐波那契数列，然后写了一个正常的斐波那契列数列
2.根据行列式，写了一个logN的斐波那契列数

#include<iostream>
#include <set>
#include <queue>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <climits>
#include <cstring>
using namespace std;
//[)
#define random1(a,b) (rand()%(b-a)+a)
//[]
#define random2(a,b) (rand()%(b-a+1)+a)
//(]
#define random3(a,b) (rand()%(b-a)+a+1)
//浮点数
#define randomFloat(a,b) (rand()/(double)RAND_MAX*(b-a)+a)


int getMax(int n)
{
    if(n < 3)
    {
        return 1;
    }
    int a = 1;
    int b = 1;
    int c = 0;
    for(int i = 2 ; i < n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
vector<vector<int>> muliMatrix(vector<vector<int>> m1, vector<vector<int>> m2);
vector<vector<int>> matrixPower (vector<vector<int>> m , int p);
//logN
int getRabbitNum(int n )
{
    if(n < 3)
    {
        return 1;
    }
    vector<vector<int>> base{{1,1},{1,0}};
    vector<vector<int>> res = matrixPower(base, n - 2);
    return res[0][0] + res[1][0];
}
vector<vector<int>> matrixPower (vector<vector<int>> m , int p)
{
    vector<vector<int>> res(m.size(),vector<int>(m[0].size()));
    //单位矩阵
    for(int i = 0; i < res.size(); i++)
    {
        res[i][i] = 1;
    }
    vector<vector<int>> tmp(m);
    while(p)
    {
        if(p & 1) res = muliMatrix(res,tmp);
        tmp = muliMatrix(tmp,tmp);
        p>>=1;
    }
    return res;
}

vector<vector<int>> muliMatrix(vector<vector<int>> m1, vector<vector<int>> m2)
{
    vector<vector<int>> res(m1.size(),vector<int>(m2[0].size()));
    for(int i = 0; i < res.size(); i++)
    {
        for(int j = 0; j < res[i].size(); j++)
        {
            for(int k = 0; k < m2.size(); k++)
            {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}



int main()
{

    int a = 0;
    while(cin>>a)
    {
        if(a != 0)
        {
//             cout<<getMax(a)<<endl;
            cout<<getRabbitNum(a)<<endl;
        }
    }

    return 0;
}