Advertisement
Guest User

Untitled

a guest
Dec 22nd, 2019
498
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef __int128_t ll;
  6.  
  7. const ll N = 119315717514047LL;
  8.  
  9. ll pow(ll base, ll exp) {
  10.   if(exp == 0)
  11.     return 1;
  12.   ll a = pow(base, exp/2);
  13.   a = a*a % N;
  14.   if(exp&1)
  15.     return (a * base)%N;
  16.   else
  17.     return a;
  18. }
  19.  
  20. ll modInverse(ll b) {
  21.   return pow(b, N-2);
  22. }
  23.  
  24. struct Mat {
  25.   ll a,b,c,d;
  26.  
  27.   Mat() {}
  28.   Mat(ll a, ll b, ll c, ll d): a(a), b(b), c(c), d(d) {}
  29.  
  30.   Mat operator*(const Mat o) const {
  31.     return Mat(
  32.       ((a*o.a + b * o.c)%N + N)%N,
  33.       ((a*o.b + b * o.d)%N + N)%N,
  34.       ((c*o.a + d * o.c)%N + N)%N,
  35.       ((c*o.b + d * o.d)%N + N)%N
  36.     );
  37.   }
  38. };
  39.  
  40. Mat antiCut(ll c) {
  41.   return Mat(1, c, 0, 1);
  42. }
  43.  
  44. Mat antiRev() {
  45.   return Mat(-1, N-1, 0, 1);
  46. }
  47.  
  48. Mat antiInc(ll num) {
  49.   return Mat(modInverse(num), 0, 0, 1);
  50. }
  51.  
  52. Mat pow(const Mat m, ll exp) {
  53.   if(exp == 0)
  54.     return Mat(1,0,0,1);
  55.   Mat ans = pow(m, exp/2);
  56.   ans = ans*ans;
  57.   if(exp&1)
  58.     return m*ans;
  59.   else
  60.     return ans;
  61. }
  62.  
  63. int main() {
  64.  
  65.   ll part2 = 0;
  66.  
  67.   Mat m(1, 0, 0, 1);
  68.  
  69.   string s;
  70.   while(cin >> s) {
  71.     if(s == "cut") {
  72.       int c;
  73.       cin >> c;
  74.       m = m*antiCut(c);
  75.     } else {
  76.       cin >> s;
  77.       if(s == "into") {
  78.         cin >> s;
  79.         cin >> s;
  80.         m = m*antiRev();
  81.       } else {
  82.         int off;
  83.         cin >> s >> off;
  84.         m = m*antiInc(off);
  85.       }
  86.     }
  87.   }
  88.  
  89.   ll exp = 101741582076661LL;
  90.  
  91.   m = pow(m, exp);
  92.  
  93.   part2 = (m.a * 2020 + m.b) % N;
  94.  
  95.   cout << ((long long) part2) << endl;
  96.  
  97.   return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement