Submission #10507304


Source Code Expand

Copy
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL




#include <algorithm>

#include <array>

#include <bitset>

#include <cassert>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

struct Scanner {
    FILE* fp = nullptr;
    char line[(1 << 15) + 1];
    size_t st = 0, ed = 0;
    void reread() {
        memmove(line, line + st, ed - st);
        ed -= st;
        st = 0;
        ed += fread(line + ed, 1, (1 << 15) - ed, fp);
        line[ed] = '\0';
    }
    bool succ() {
        while (true) {
            if (st == ed) {
                reread();
                if (st == ed) return false;
            }
            while (st != ed && isspace(line[st])) st++;
            if (st != ed) break;
        }
        if (ed - st <= 50) reread();
        return true;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        while (true) {
            size_t sz = 0;
            while (st + sz < ed && !isspace(line[st + sz])) sz++;
            ref.append(line + st, sz);
            st += sz;
            if (!sz || st != ed) break;
            reread();
        }
        return true;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        ref = T(0);
        while (isdigit(line[st])) {
            ref = 10 * ref + (line[st++] - '0');
        }
        if (neg) ref = -ref;
        return true;
    }
    template <class T> bool read_single(V<T>& ref) {
        for (auto& d : ref) {
            if (!read_single(d)) return false;
        }
        return true;
    }
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
    Scanner(FILE* _fp) : fp(_fp) {}
};

struct Printer {
  public:
    template <bool F = false> void write() {}
    template <bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(' ');
        write_single(h);
        write<true>(t...);
    }
    template <class... T> void writeln(const T&... t) {
        write(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fp(_fp) {}
    ~Printer() { flush(); }

  private:
    static constexpr size_t SIZE = 1 << 15;
    FILE* fp;
    char line[SIZE], small[50];
    size_t pos = 0;
    void flush() {
        fwrite(line, 1, pos, fp);
        pos = 0;
    }
    void write_single(const char& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    void write_single(T val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val; // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char('0' + (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }
    void write_single(const string& s) {
        for (char c : s) write_single(c);
    }
    void write_single(const char* s) {
        size_t len = strlen(s);
        for (size_t i = 0; i < len; i++) write_single(s[i]);
    }
    template <class T> void write_single(const V<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
};
Scanner sc(stdin);
Printer pr(stdout);

struct Nimber64;
Nimber64 mul_naive(Nimber64 l, Nimber64 r);
struct Nimber64 {
    const static V<ull> factor;
    const static array<array<unsigned char, 256>, 256> small;
    const static array<array<array<Nimber64, 256>, 8>, 8> precalc;
    ull v;
    Nimber64() : v(0) {}
    Nimber64(ull _v) : v(_v) {}
    const Nimber64 operator+(Nimber64 r) const {
        return v ^ r.v;
    }
    const Nimber64 operator*(Nimber64 r) const {
        Nimber64 ans;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                ull x = (v >> (8 * i)) % 256;
                ull y = (r.v >> (8 * j)) % 256;
                ans += precalc[i][j][small[x][y]];
            }
        }
        return ans;
    }
    bool operator==(Nimber64 r) const {
        return v == r.v;
    }
    Nimber64& operator+=(Nimber64 r) { return *this = *this + r; }
    Nimber64& operator*=(Nimber64 r) { return *this = *this * r; }

    Nimber64 pow(ull n) const {
        Nimber64 x = *this, r = 1;
        while (n) {
            if (n & 1) r = r * x;
            x = x * x;
            n >>= 1;
        }
        return r;
    }

    ull discrete_logarithm(Nimber64 y) {
        ull rem = 0, mod = 1;
        for (ull p : factor) {
            ull STEP = 1;
            while (4 * STEP * STEP < p) STEP *= 2;
            auto inside = [&](Nimber64 x, Nimber64 y) {
                unordered_map<ull, int> mp;
                Nimber64 big = 1; // x^m
                for (int i = 0; i < int(STEP); i++) {
                    mp[y.v] = i;
                    y *= x;
                    big *= x;
                }
                Nimber64 now = 1;
                for (int step = 0; step < int(p + 10); step += STEP) {
                    now *= big;
                    // check [step + 1, step + STEP]
                    if (mp.find(now.v) != mp.end()) {
                        return (step + STEP) - mp[now.v];
                    }
                }
                return ull(-1);
            };

            ull q = ull(-1) / p;
            ull res = inside((*this).pow(q), y.pow(q));
            if (res == ull(-1)) {
                return ull(-1);
            }
            res %= p;
            // mod p = v
            if (mod == 1) {
                rem = res;
                mod = p;
            } else {
                while (rem % p != res) rem += mod;
                mod *= p;
            }
        }
        return rem;
    }

    bool is_primitive_root() const {
        for (ull p : factor) {
            if ((*this).pow(ull(-1) / p).v == 1) return false;
        }
        return true;
    }
};
const V<ull> Nimber64::factor = {
    6700417, 65537, 641, 257, 17, 5, 3,
};

Nimber64 mul_naive(Nimber64 l, Nimber64 r) {
    ull a = l.v, b = r.v;
    if (a < b) swap(a, b);
    if (b == 0) return 0;
    if (b == 1) return a;
    int p = 32;
    while (max(a, b) < (1ULL << p)) p /= 2;
    ull power = 1ULL << p;
    if (a >= power && b >= power) {
        Nimber64 ans;
        ans += mul_naive(a % power, b % power);
        ans += mul_naive(a / power, b % power).v * power;
        ans += mul_naive(a % power, b / power).v * power;
        auto x = mul_naive(a / power, b / power);
        ans += x.v * power;
        ans += mul_naive(x.v, power / 2);
        return ans;
    } else {
        return Nimber64(mul_naive(a / power, b).v * power) + mul_naive(a % power, b);
    }
};

const array<array<unsigned char, 256>, 256> Nimber64::small = []() {
    array<array<unsigned char, 256>, 256> small;
    for (int i = 0; i < 256; i++) {
        for (int j = 0; j < 256; j++) {
            small[i][j] = (unsigned char)(mul_naive(i, j).v);
        }
    }
    return small;
}();

const array<array<array<Nimber64, 256>, 8>, 8> Nimber64::precalc = []() {
    array<array<array<Nimber64, 256>, 8>, 8> precalc;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            for (int k = 0; k < 256; k++) {
                precalc[i][j][k] = mul_naive(mul_naive(1ULL << (8 * i), 1ULL << (8 * j)), k);
            }
        }
    }
    return precalc;
}();

using Int = __int128;
Int gcd(Int a, Int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (b == 0) return a;
    return gcd(b, a % b);
}

/// g:gcd(a, b), ax+by=g
struct EG { Int g, x, y; };
EG ext_gcd(Int a, Int b) {
    if (b == 0) {
        if (a >= 0) return EG{a, 1, 0};
        else return EG{-a, -1, 0};
    } else {
        auto e = ext_gcd(b, a % b);
        return EG{e.g, e.y, e.x - a / b * e.y};
    }
}

Int inv_mod(Int x, Int md) {
    auto z = ext_gcd(x, md).x;
    return (z % md + md) % md;
}

const ll OFF = 3 * TEN(17);

int main() {
    const Int MOD = ull(-1);
    Nimber64 a = (6 | 1ULL << 32);
    Nimber64 b = (10 | 1ULL << 34);
    assert(a.is_primitive_root());
    assert(b.is_primitive_root());
    Int s = a.discrete_logarithm(a + 1);
    Int t = b.discrete_logarithm(b + 1);
    Int diff = s - t;
    assert(gcd(diff, MOD) == 1);

    int n;
    sc.read(n);
    V<ll> x(n), y(n);
    for (int i = 0; i < n; i++) {
        sc.read(x[i], y[i]);
        x[i] += OFF; y[i] += OFF;
    }
    auto f = [&](Nimber64 z) {
        Nimber64 sum;
        for (int i = 0; i < n; i++) {
            sum += z.pow(x[i]) * (z + 1).pow(y[i]);
        }
        return sum;
    };

    // X + s * Y
    Int u = a.discrete_logarithm(f(a));
    // X + t * Y
    Int v = b.discrete_logarithm(f(b));

    Int Y = (u - v) * inv_mod(s - t, MOD);
    Y = (Y % MOD + MOD) % MOD;
    Int X = u - s * Y;
    X = (X % MOD + MOD) % MOD;

    pr.writeln(ll(X) - OFF, ll(Y) - OFF);
    return 0;
}

Submission Info

Submission Time
Task C2 - Triangular Lamps Hard
User yosupo
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 10247 Byte
Status
Exec Time 427 ms
Memory 896 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt
All 1000 / 1000 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, 074.txt, 075.txt, 076.txt, 077.txt, 078.txt, 079.txt, 080.txt, 081.txt, 082.txt, 083.txt, 084.txt, 085.txt, 086.txt, 087.txt, 088.txt, 089.txt, 090.txt, 091.txt, 092.txt, 093.txt, 094.txt, 095.txt, 096.txt, 097.txt, 098.txt, 099.txt, example0.txt
Case Name Status Exec Time Memory
000.txt 360 ms 768 KB
001.txt 392 ms 768 KB
002.txt 379 ms 768 KB
003.txt 362 ms 768 KB
004.txt 372 ms 768 KB
005.txt 427 ms 896 KB
006.txt 376 ms 768 KB
007.txt 398 ms 768 KB
008.txt 361 ms 768 KB
009.txt 378 ms 768 KB
010.txt 393 ms 768 KB
011.txt 362 ms 768 KB
012.txt 382 ms 768 KB
013.txt 382 ms 768 KB
014.txt 365 ms 768 KB
015.txt 361 ms 768 KB
016.txt 358 ms 768 KB
017.txt 380 ms 768 KB
018.txt 368 ms 768 KB
019.txt 363 ms 768 KB
020.txt 361 ms 768 KB
021.txt 370 ms 768 KB
022.txt 379 ms 768 KB
023.txt 359 ms 768 KB
024.txt 375 ms 768 KB
025.txt 393 ms 768 KB
026.txt 361 ms 768 KB
027.txt 379 ms 768 KB
028.txt 364 ms 768 KB
029.txt 362 ms 768 KB
030.txt 378 ms 768 KB
031.txt 378 ms 768 KB
032.txt 363 ms 768 KB
033.txt 364 ms 768 KB
034.txt 347 ms 768 KB
035.txt 366 ms 768 KB
036.txt 376 ms 768 KB
037.txt 362 ms 768 KB
038.txt 360 ms 768 KB
039.txt 380 ms 768 KB
040.txt 362 ms 768 KB
041.txt 388 ms 768 KB
042.txt 411 ms 768 KB
043.txt 368 ms 768 KB
044.txt 377 ms 768 KB
045.txt 363 ms 768 KB
046.txt 360 ms 768 KB
047.txt 389 ms 768 KB
048.txt 360 ms 768 KB
049.txt 368 ms 768 KB
050.txt 362 ms 768 KB
051.txt 364 ms 768 KB
052.txt 364 ms 768 KB
053.txt 361 ms 768 KB
054.txt 364 ms 768 KB
055.txt 362 ms 768 KB
056.txt 361 ms 768 KB
057.txt 382 ms 768 KB
058.txt 365 ms 768 KB
059.txt 362 ms 768 KB
060.txt 363 ms 768 KB
061.txt 367 ms 768 KB
062.txt 416 ms 768 KB
063.txt 362 ms 768 KB
064.txt 370 ms 768 KB
065.txt 362 ms 768 KB
066.txt 362 ms 768 KB
067.txt 361 ms 768 KB
068.txt 391 ms 768 KB
069.txt 378 ms 768 KB
070.txt 359 ms 768 KB
071.txt 366 ms 768 KB
072.txt 364 ms 768 KB
073.txt 362 ms 768 KB
074.txt 409 ms 768 KB
075.txt 380 ms 768 KB
076.txt 386 ms 768 KB
077.txt 363 ms 768 KB
078.txt 378 ms 768 KB
079.txt 380 ms 768 KB
080.txt 362 ms 768 KB
081.txt 363 ms 768 KB
082.txt 358 ms 768 KB
083.txt 366 ms 768 KB
084.txt 366 ms 768 KB
085.txt 364 ms 768 KB
086.txt 393 ms 768 KB
087.txt 365 ms 768 KB
088.txt 408 ms 768 KB
089.txt 367 ms 768 KB
090.txt 397 ms 768 KB
091.txt 361 ms 768 KB
092.txt 368 ms 768 KB
093.txt 360 ms 768 KB
094.txt 361 ms 768 KB
095.txt 368 ms 768 KB
096.txt 407 ms 768 KB
097.txt 364 ms 768 KB
098.txt 372 ms 768 KB
099.txt 390 ms 768 KB
example0.txt 57 ms 512 KB