-
Notifications
You must be signed in to change notification settings - Fork 2
/
fibonacci.cpp
67 lines (57 loc) · 1.34 KB
/
fibonacci.cpp
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 7, /*MOD = 1e9 + 7,*/ INF = numeric_limits<int>::max();
const long double PI = acos(-1);
const double EPS = 0.000000001;
int m;
template <typename T>
T BinPow(T a, int n) {
if (n == 1) {
return a;
}
if (n & 1) {
return a * BinPow(a, n - 1);
}
T b = BinPow(a, n / 2);
return b * b;
}
class Fibonachi {
public:
Fibonachi() : m_({{1, 1}, {1, 0}}) {}
Fibonachi operator*(const Fibonachi& t) {
vector<vector<int>> a(2, vector<int>(2));
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
a[i][j] += ((m_[i][k] % m) * (t.m_[k][j] % m)) % m;
a[i][j] %= m;
}
}
}
m_ = a;
return *this;
}
Fibonachi operator%(const int& n) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
m_[i][j] %= n;
}
}
return *this;
}
int operator[](const pair<int, int>& i) {
return m_[i.first][i.second];
}
private:
vector<vector<int>> m_;
};
signed main() {
int n;
cin >> n;
cin >> m;
Fibonachi t;
t = BinPow(t, n);
cout << t[{0, 1}];
return 0;
}