• + 0 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;
    }