Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef __int128_t ll;
- const ll N = 119315717514047LL;
- ll pow(ll base, ll exp) {
- if(exp == 0)
- return 1;
- ll a = pow(base, exp/2);
- a = a*a % N;
- if(exp&1)
- return (a * base)%N;
- else
- return a;
- }
- ll modInverse(ll b) {
- return pow(b, N-2);
- }
- struct Mat {
- ll a,b,c,d;
- Mat() {}
- Mat(ll a, ll b, ll c, ll d): a(a), b(b), c(c), d(d) {}
- Mat operator*(const Mat o) const {
- return Mat(
- ((a*o.a + b * o.c)%N + N)%N,
- ((a*o.b + b * o.d)%N + N)%N,
- ((c*o.a + d * o.c)%N + N)%N,
- ((c*o.b + d * o.d)%N + N)%N
- );
- }
- };
- Mat antiCut(ll c) {
- return Mat(1, c, 0, 1);
- }
- Mat antiRev() {
- return Mat(-1, N-1, 0, 1);
- }
- Mat antiInc(ll num) {
- return Mat(modInverse(num), 0, 0, 1);
- }
- Mat pow(const Mat m, ll exp) {
- if(exp == 0)
- return Mat(1,0,0,1);
- Mat ans = pow(m, exp/2);
- ans = ans*ans;
- if(exp&1)
- return m*ans;
- else
- return ans;
- }
- int main() {
- ll part2 = 0;
- Mat m(1, 0, 0, 1);
- string s;
- while(cin >> s) {
- if(s == "cut") {
- int c;
- cin >> c;
- m = m*antiCut(c);
- } else {
- cin >> s;
- if(s == "into") {
- cin >> s;
- cin >> s;
- m = m*antiRev();
- } else {
- int off;
- cin >> s >> off;
- m = m*antiInc(off);
- }
- }
- }
- ll exp = 101741582076661LL;
- m = pow(m, exp);
- part2 = (m.a * 2020 + m.b) % N;
- cout << ((long long) part2) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement