題目連結:https://acm.cs.nthu.edu.tw/problem/10322/

一題矩陣快速冪裸題(題目就表明(?)

當然是好好地把矩陣的乘法定義定好，注意一些0/1擺放的細節，把其套上快速冪的模板，就大功告成了。><

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define int long long int
#define jizz ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL);
#define pb push_back
#define po pop_back;
#define F first
#define S second
#define CN cout<<"\n"
#define m 100000007
using namespace std;
typedef array<array<int,2>,2> Matrix;
Matrix operator*(Matrix A , Matrix B)
{
    Matrix C;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            C[i][j]=0;
            for(int k=0;k<2;k++)
                C[i][j]=(C[i][j]%m+(A[i][k]%m*B[k][j]%m)%m)%m;
        }
    }
    return C;
}
Matrix power(Matrix A,int n)
{
    Matrix ans={{{1,0},{0,1}}};
    while(n)
    {
        if(n&1)
            ans=ans*A;
        n>>=1;
        A=A*A;
    }
    return ans;
}
signed main()
{
    jizz;
    int num;
    while(cin >> num || num==0)
    { 
        if(num==0)
        {
            cout << 0 <<"\n";
            continue;
        }
        else if(num==-1)
            break;
        else
        {
            Matrix A={{{1,1},{1,0}}};
            Matrix C=power(A,num-1);
            cout << C[0][0] <<"\n";
        }
    }
    return 0;
}