You are viewing a single comment's thread. Return to all comments →
C++ solution
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef pair<ll, ll> pii; typedef vector<pii> vii; typedef vector<vii> vvll; const int mod = 1000000007; int w[] = {0, 1, 4, 5}; int u[] = {2, 3, 6, 7}; ll mpow (ll x, ll n){ ll res = 1; while(n){ if(n & 1) res = res * x % mod; n /= 2; x = x * x % mod; } return res; } ll inv(ll x){ return mpow(x, mod - 2); } vvl id(int k){ vvl v(k, vl(k)); for(int i = 0; i < k; ++i) v[i][i] = 1; return v; } vvl mul(const vvl &x, const vvl &y){ int n = x.size(); vvl res(n, vl(n)); for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; j += 1){ for(int l = 0; l < 4; ++l){ res[w[i]][w[j]] += x[w[i]][w[l]]*y[w[l]][w[j]]; res[u[i]][u[j]] += x[u[i]][u[l]]*y[u[l]][u[j]]; } res[w[i]][w[j]] %= mod; res[u[i]][u[j]] %= mod; } return res; } vvl mulfast(const vvl &x, const vvl &y){ int n = x.size(); vvl res(n, vl(n)); for(int i = 0; i < 4; ++i){ for(int j = 0; j < 4; j += 2){ for(int l = 0; l < 4; ++l){ res[w[i]][w[j]] += x[w[i]][w[l]] * y[w[l]][w[j]]; } res[w[i]][w[j]] %= mod; } } for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; j += 2){ res[u[i]][u[j]] = res[w[i]][w[j]]; } for(int i = 1; i < 4; i += 2) for(int j = 1; j < 4; j += 2){ res[w[i]][w[j]] = res[w[i - 1]][w[j - 1]]; res[u[i]][u[j]] = res[u[i - 1]][u[j - 1]]; } for(int i = 0; i < 4; i += 2) for(int j = 1; j < 4; j += 2){ res[w[i]][w[j]] = -res[w[i + 1]][w[j - 1]]; res[u[i]][u[j]] = -res[u[i + 1]][u[j - 1]]; } return res; } ll in(){ ll x, y; scanf("%lld/%lld", &x, &y); return x * inv(y) % mod; } void out(const vl & v){ for(int i = 0; i < v.size(); ++i) cerr << v[i] << ' '; cerr << endl; } void out(const vvl & v){ cerr << endl; for(int i = 0; i < v.size(); ++i) out(v[i]); } void eval(ll x, ll y, const vvl & a){ vl t(8); for(int i = 0; i < 8; ++i) t[i] = (a[i][0]+a[i][6]) % mod; ll xz = (t[6] + t[4] * x - t[5] * y) % mod; ll yz = (t[7] + t[4] * y + t[5] * x) % mod; if(xz == 0 && yz == 0){ printf("WONDERLAND\n"); } else{ ll xn = (t[2] + t[0] * x - t[1] * y) % mod; ll yn = (t[3] + t[0] * y + t[1] * x) % mod; ll d = (xz * xz + yz * yz) % mod; assert(d); ll di = inv(d); ll xf = ((xz * xn + yz * yn) % mod * di % mod + mod) % mod; ll yf = ((-yz * xn + xz * yn) % mod * di % mod + mod) % mod; printf("%lld %lld\n", xf, yf); } } pii mul(pii x, pii y){ return pii((x.first * y.first - x.second * y.second) % mod, (y.first * x.second + y.second * x.first) % mod); } void mul(pii & z, pii x, pii y){ z.first = (z.first + x.first * y.first - x.second * y.second) % mod; z.second = (z.second + y.first * x.second + y.second * x.first) % mod; } pii mpow(pii x, ll n){ pii res(1, 0); while(n){ if(n & 1) res = mul(res, x); x = mul(x, x); n /= 2; } return res; } vvll mul(vvll x, vvll y){ int n = x.size(); vvll res(n, vii(n)); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) for(int l = 0; l < n; ++l) mul(res[i][j], x[i][l], y[l][j]); return res; } vvl mpow(vvl x, ll n){ vvll res(2, vii(2)); res[0][0] = res[1][1] = pii(1, 0); vvll y(2, vii(2)); for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) y[i][j] = pii(x[i * 4][j * 4], x[i * 4][j * 4 + 1]); while(n){ if(n & 1) res = mul(res, y); y = mul(y, y); n /= 2; } vvl resout(8, vl(8)); for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j){ resout[i * 4][j * 4] = res[i][j].first; resout[i * 4 + 1][j * 4 + 1] = res[i][j].first; resout[i * 4][j * 4 + 1] = res[i][j].second; resout[i * 4 + 1][j * 4] = -res[i][j].second; } for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; j++){ resout[u[i]][u[j]] = resout[w[i]][w[j]]; } return resout; } int main(){ int T; cin >> T; for(int test = 1; test <= T; ++test){ ll n, k, x, y; scanf("%lld%lld", &n, &k); x = in(); y = in(); int cntc = 0; vvl a = id(8); char type; ll a1, b, c; for(int i = 0; i < n; ++i){ scanf("\n%c", &type); if(type == 'I'){ cntc = 1 - cntc; vvl x(8, vl(8)); for(int i = 0; i < 4; i += 2) x[i][i + 4] = x[i + 4][i] = 1; for(int i = 1; i < 4; i += 2) x[i][i + 4] = x[i + 4][i] = -1; a = mul(x, a); } else if(type == 'F'){ cntc = 1 - cntc; char ax; scanf(" %c", &ax); vvl x = id(8); for(int i = 0; i < 4; ++i) x[2 * i][2 * i] = -1; if(ax == 'Y'){ for(int i = 0; i < 4; ++i) x[i][i] *= -1; } a = mul(x, a); } else if(type == 'S'){ c = in(); vvl x = id(8); for(int i = 0; i < 4; ++i) x[i][i] = c; a = mul(x, a); } else if(type == 'R'){ a1 = in(); b = in(); vvl x = id(8); for(int i = 0; i < 4; i += 2){ x[i][i] = a1; x[i][i + 1] = b; x[i + 1][i] = -b; x[i + 1][i + 1] = a1; } a = mul(x, a); } else if(type == 'T'){ a1 = in(); b = in(); vvl x = id(8); for(int i = 0; i < 4; i += 2){ x[i][i + 4] = a1; x[i][i + 5] = -b; x[i + 1][i + 4] = b; x[i + 1][i + 5] = a1; } a = mul(x, a); } else{ cerr << i << ' ' << type << endl; assert(0); } } if(n == 1){ if(type == 'F' || type == 'I'){ k %= 2; } else if(type == 'S'){ a = id(8); for(int i = 0; i < 4; ++i) a[i][i] = mpow(c, k); k = 1; } else if(type == 'T'){ x = (x + k % mod * a1) % mod; y = (y + k % mod * b) % mod; k = 0; } else if(type == 'R'){ pii t(a1, -b); t = mpow(t, k); a1 = t.first; b = -t.second; a = id(8); for(int i = 0; i < 4; i += 2){ a[i][i] = a1; a[i][i + 1] = b; a[i + 1][i] = -b; a[i + 1][i + 1] = a1; } k = 1; } } vvl a0 = a; a = mul(a, a); a = mpow(a, k / 2); if(k % 2) a = mul(a, a0); if(k % 2 && cntc){ y *= -1; } eval(x, y, a); } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Down the Rabbit Hole
You are viewing a single comment's thread. Return to all comments →
C++ solution