Sort by

recency

|

4 Discussions

|

  • + 0 comments

    When you know Moebius transformations and check that you can work in Fp (with ), it's quite simple but laborious.
    Seems like no one succeded in Python before me (see leaderboard), so here a remark:
    I at first used some nice and clean classes to encapsulate

    • Fp with its arithmetic operations
    • Complex arithmetics (operating on pairs eg of type Fp)
    • Moebius transforms with multiplication and power

    Alas this solution was too slow for test cases 9ff, so i refactored it, completely removed any classes and subfunctions, to end up with simple (long!!) completely explicite formulas. This did it for all tests.

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

    This is best description to understand the Alica story in the bank of the river about rabbit hole which I'm too motivated to read such adventure news. And now we all know that live games are the most attractive option at iCasinoReviews - Best real money online casinos list in NZ that roulette are all available in live formats.

  • + 1 comment

    Um... what sort of strange modulo arithmetic is the author using in the example? Last I checked 119/1160 = 0.10258620689655172 (mod any numer greater than 1)

    Anyone know what operation is actually being performed to get 881896558?

No more comments