Submission #428573

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

/**
 * 行列ライブラリ with Mod
 */
template<int N, int M>
struct MatrixMod2 {
    array<bitset<M>, N> d;

    MatrixMod2() {
        for (int i = 0; i < N; i++) {
            d[i].reset();
        }
    }

    bitset<M>& operator[](int p) {
        return d[p];
    }
    
    const bitset<M>& operator[](int p) const {
        return d[p];
    }
    
    MatrixMod2& operator=(const MatrixMod2 &other) {
        d = other.d;
        return *this;
    }

    MatrixMod2 operator+(const MatrixMod2 &right) {
        MatrixMod2 res(N, M);
        for (int i = 0; i < N; i++) {
            res[i] = d[i]^right[i];
        }
        return res;
    }
    
    template<int K>
    MatrixMod2<N, K> operator*(const MatrixMod2<M, K> &right) {
        MatrixMod2<N, K> res;
        MatrixMod2<K, M> r;
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < M; j++) {
                r[i][j] = right[j][i]; 
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                res[i][j] = (d[i]&r[j]).count() % 2;
            }
        }
        return res;
    }

    template<int K>
    MatrixMod2<N, K> trans_mul(const MatrixMod2<K, M> &r) {
        MatrixMod2<N, K> res;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                res[i][j] = (d[i]&r[j]).count() % 2;
            }
        }
        return res;
    }

    MatrixMod2 pow(ll p) {
        assert(N == M);
        MatrixMod2<N, M> res, buf = *this;
        for (int i = 0; i < N; i++) res[i][i] = true;
        while(p != 0) {
            if (p % 2) {
                res = res*buf;
            }
            p /= 2;
            buf = buf*buf;
        }
        return res;
    }

    MatrixMod2<M, N> transposed() {
        MatrixMod2<M, N> res;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                res[j][i] = d[i][j];
            }
        }
        return res;
    }
};

ull a, b, x;

bool solve1() {
    ull aa = a;
    unordered_set<ull> s;
    for (int i = 0; i < (1<<19); i++) {
        if (s.count(aa)) {
            printf("-1\n");
            return true;
        }
        s.insert(aa);
        if (aa == x) {
            printf("%d\n", i);
            return true;
        }
        aa = (aa/2) ^ (aa % 2 * b);
    }
    return false;
}

MatrixMod2<40, 40> base, bigB;


MatrixMod2<1, 40> m;

ull next(ull aa) {
    m[0] = bitset<40>(aa);
    return (m.trans_mul(bigB))[0].to_ullong();
}


MatrixMod2<40, 40> powt[60];

ull succ(ull aa, ll t) {
    m[0] = bitset<40>(aa);
    int i = 0;
    while (t) {
        if (t & 1) {
            m = m.trans_mul(powt[i]);
        }
        i++;
        t /= 2;
    }
    return m[0].to_ullong();
}

int main() {
    cin >> a >> b >> x;

    if (solve1()) return 0;

    for (int i = 0; i < 39; i++) {
        base[i+1][i] = true;
    }

    base[0] = bitset<40>(b);

    bigB = base.pow(1<<18).transposed();

    for (int i = 0; i < 50; i++) {
        powt[i] = base.pow(1ULL<<i).transposed();
    }

    unordered_map<ull, int> mp;
    ull xx = x;
    for (int i = 0; i < (1<<18); i++) {
        mp[xx] = i;
        xx = (xx/2) ^ (xx % 2 * b);
    }


    ull aa = a;
    for (ll i = 0; i <= (1<<18); i++) {
        if (i && mp.count(aa)) {
            if (succ(a, i * (1<<18) - mp[aa]) == x) {
                printf("%lld\n", i * (1<<18) - mp[aa]);
                return 0;
            }
        }
        aa = next(aa);
    }
    printf("-1\n");
    return 0;
}

Submission Info

Judge Result