SHARE
TWEET

R

anon20016 Oct 21st, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <set>
  3. #include <map>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. #define li long long
  10.  
  11.  
  12.  
  13. vector<vector<li> > mul(vector<vector<li> > a, vector<vector<li> > b, li m) {
  14.     vector<vector<li> > c(a.size(), vector<li>(b[0].size(), 0));
  15.     for (int i = 0; i < a.size(); i++) {
  16.         for (int j = 0; j < b[0].size(); j++) {        
  17.             for (int k = 0; k < b.size(); k++) {
  18.                 c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
  19.             }
  20.         }
  21.     }
  22.     return c;
  23. }
  24.  
  25. vector<vector<li> > binpow(vector<vector<li> > a, li n, li m) {
  26.     vector<vector<li> > res(a.size(), vector<li>(a.size(), 0));
  27.     for (int i = 0; i < a.size(); i++) {
  28.         res[i][i] = 1;
  29.     }
  30.     while (n) {
  31.         if (n & 1)
  32.             res = mul(res, a, m);          
  33.         a = mul(a, a, m);
  34.         n >>= 1;
  35.     }
  36.     return res;
  37. }
  38.  
  39. int main() {
  40.     li n, m;
  41.     cin >> n >> m;
  42.     vector<vector<li> > a(2);
  43.     a[0].push_back(0);
  44.     a[0].push_back(1);
  45.     a[1].push_back(1);
  46.     a[1].push_back(1);
  47.     if (n == 0) {
  48.         cout << 0 % m;
  49.         return 0;
  50.     }
  51.     vector<vector<li> > s = binpow(a, n, m);
  52.     cout << s[0][1];
  53.     return 0;
  54. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top