11022: 【原1022】Fib数列

题目

题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1022

Description

定义Fib数列：\( 1,1,2,3,5,8,13,\dots \)

求第\(N\)项除以\(2010\)的余数

Input Format

输入仅一行，为一个整数\(N\)

Output Format

输出仅一行，为第\(N\)项除以\(2010\)的余数

Sample Input

3

Sample Output

2

Limits:

对于70%的数据 \( N \leq 1,000,000 \)

对于100%的数据 \( N \leq 210,000,000,000 \)

FineArtz's solution

/* Fib数列 */
#include <iostream>
using namespace std;

const int MOD = 2010;

class Mat{
public:
    //constructor
    Mat(const int &x, const int &y, const int &p, const int &q)
        : a11(x), a12(y), a21(p), a22(q) {}
    Mat() : Mat(0, 0, 0, 0) {};
    Mat(const Mat &m) : a11(m.a11), a12(m.a12), a21(m.a21), a22(m.a22) {};

    long long a11, a12, a21, a22;
};
Mat operator *(const Mat &lhs, const Mat &rhs){
    long long a11 = (lhs.a11 * rhs.a11 + lhs.a12 * rhs.a21) % MOD;
    long long a12 = (lhs.a11 * rhs.a12 + lhs.a12 * rhs.a22) % MOD;
    long long a21 = (lhs.a21 * rhs.a11 + lhs.a22 * rhs.a21) % MOD;
    long long a22 = (lhs.a21 * rhs.a12 + lhs.a22 * rhs.a22) % MOD;
    return Mat(a11, a12, a21, a22);
}

Mat QuickPow(Mat a, long long pow){
    Mat ret(1, 0, 0, 1);
    while (pow != 0){
        if (pow & 1) ret = ret * a;
        a = a * a;
        pow >>= 1;
    }
    return ret;
}

int main(){
    long long n;
    cin >> n;
    if (n == 1 || n == 2){
        cout << 1 << endl;
        return 0;
    }
    Mat f0(1, 0, 1, 0), f(1, 1, 1, 0);
    Mat ans = QuickPow(f, n - 2);
    cout << (ans.a11 + ans.a12) % MOD << endl;
    return 0;
}