Submission #2331330

---

Source Code Expand

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
constexpr ll MOD = 1000000007LL;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
template <typename Functor>
struct fix_type
{
    Functor functor;
    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const& { return functor(functor, std::forward<Args>(args)...); }
};
template <typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor) { return {std::forward<Functor>(functor)}; }

template <int N>
using BitVector = bitset<N>;  // [a_(N-1),a_(N-2),...,a_1,a_0] であることに注意
template <int N>
using BitMatrix = vector<BitVector<N>>;
// m_0   = [m_0(N-1)    ,m_0(N-2)    , ... ,m_01    ,m_00]
// m_1   = [m_1(N-1)    ,m_1(N-2)    , ... ,m_11    ,m_10]
// ...
// m_N-1 = [m_(N-1)(N-1),m_(N-1)(N-2), ... ,m_(N-1)1,m_(N-1)0] であることに注意

template <int N>
BitMatrix<N> transposed(const BitMatrix<N>& mat)
{
    assert(mat.size() == N);
    BitMatrix<N> ans(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) { ans[i][j] = mat[N - 1 - j][N - 1 - i]; }
    }
    return ans;
}

template <int N>
BitMatrix<N> mul(const BitMatrix<N>& a, const BitMatrix<N>& b)
{
    assert(a.size() == N);
    assert(b.size() == N);
    const auto bt = transposed<N>(b);
    BitMatrix<N> ans(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) { ans[i][N - 1 - j] = (a[i] & bt[j]).count() % 2; }
    }
    return ans;
}

template <int N>
BitVector<N> mul(const BitMatrix<N>& m, const BitVector<N>& v)
{
    assert(m.size() == N);
    BitVector<N> ans(N);
    for (int i = 0; i < N; i++) { ans[N - 1 - i] = (m[i] & v).count() % 2; }
    return ans;
}

template <int N>
static BitMatrix<N> UnitBitMatrix()
{
    BitMatrix<N> ans(N);
    for (int i = 0; i < N; i++) { ans[i][N - 1 - i] = 1; }
    return ans;
}

template <int N>
BitMatrix<N> power(const BitMatrix<N>& mat, const ll n)
{
    if (n == 0) { return UnitBitMatrix<N>(); }
    if (n % 2 == 1) {
        return mul<N>(power<N>(mat, n - 1), mat);
    } else {
        const auto pp = power<N>(mat, n / 2);
        return mul<N>(pp, pp);
    }
}

int main()
{
    constexpr int N = 36;
    ull A, B, X;
    cin >> A >> B >> X;
    const BitVector<N> a(A);
    const BitVector<N> x(X);
    BitMatrix<N> mat(N);
    for (int i = 1; i < N; i++) { mat[i][N - i] = 1; }
    for (int i = 0; i < N; i++) { mat[N - 1 - i][0] = (B >> i) & 1; }
    constexpr ll SQRT = 1LL << 18;
    const BitMatrix<N> MS = power<N>(mat, SQRT);
    map<ull, ll> mp;
    BitVector<N> av = mul<N>(MS, a);
    for (ll i = 1; i <= SQRT; i++) {
        const ull v = av.to_ullong();
        if (mp.find(v) == mp.end()) { mp[v] = i * SQRT; }
        av = mul<N>(MS, av);
    }
    BitVector<N> xv = x;
    ll ans = INF<ll>;
    for (ll i = 0; i < SQRT; i++) {
        const ull v = xv.to_ullong();
        if (mp.find(v) != mp.end() and mp[v] >= i) { ans = min(ans, mp[v] - i); }
        xv = mul<N>(mat, xv);
    }
    if (ans == INF<ll>) {
        cout << -1 << endl;
    } else {
        if (mul<N>(power<N>(mat, ans), a).to_ullong() == x.to_ullong()) {
            cout << ans << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

Submission Info

Judge Result