Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <map>
- #include <vector>
- #include <algorithm>
- using namespace std;
- #define li long long
- vector<vector<li> > mul(vector<vector<li> > a, vector<vector<li> > b, li m) {
- vector<vector<li> > c(a.size(), vector<li>(b[0].size(), 0));
- for (int i = 0; i < a.size(); i++) {
- for (int j = 0; j < b[0].size(); j++) {
- for (int k = 0; k < b.size(); k++) {
- c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
- }
- }
- }
- return c;
- }
- vector<vector<li> > binpow(vector<vector<li> > a, li n, li m) {
- vector<vector<li> > res(a.size(), vector<li>(a.size(), 0));
- for (int i = 0; i < a.size(); i++) {
- res[i][i] = 1;
- }
- while (n) {
- if (n & 1)
- res = mul(res, a, m);
- a = mul(a, a, m);
- n >>= 1;
- }
- return res;
- }
- int main() {
- li n, m;
- cin >> n >> m;
- vector<vector<li> > a(2);
- a[0].push_back(0);
- a[0].push_back(1);
- a[1].push_back(1);
- a[1].push_back(1);
- if (n == 0) {
- cout << 0 % m;
- return 0;
- }
- vector<vector<li> > s = binpow(a, n, m);
- cout << s[0][1];
- return 0;
- }
Add Comment
Please, Sign In to add comment