提出 #373307

---

ソースコード 拡げる

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <utility>
#include <vector>
using namespace std;

#define M (1<<18)

inline long long next(long long x, long long B) {
    return (x >> 1) ^ ((x & 1) * B);
}

inline long long supernext(long long x, const vector<long long> &B) {
    long long ret = 0;
    for (size_t i = 0; i < B.size(); ++i) {
        ret ^= ((x >> i) & 1) * B[i];
    }
    return ret;
}

inline long long prev(long long x, long long B, int Bs) {
    return (x << 1) ^ (((x >> Bs) & 1) * (B * 2 + 1));
}

long long solve0(long long A, long long B, long long X) {
    long long x;

    x = A;
    for (int i = 0; i < M * 100; ++i) {
        if (x == X) {
            return i;
        }
        x = next(x, B);
    }
    return -1;
}

long long solve(long long A, long long B, long long X) {
    long long x;
    map<long long, int> offset;

    x = A;
    for (int i = 0; i < M; ++i) {
        if (x == X) {
            return i;
        }
        x = next(x, B);
    }

    int Bs = 0;
    for (int i = 0; i < 40; ++i) {
        if ((1LL << i) & B) {
            Bs = i;
        }
    }

    if (X >= (2LL<<Bs)) {
        return -1;
    }

    x = X;
    for (int i = 0; i < M; ++i) {
        if (offset.count(x) == 0)
            offset[x] = i;
        x = prev(x, B, Bs);
    }

    int mat[36][36];
    memset(mat, 0x00, sizeof(mat));
    for (int i = 0; i < 36; ++i) {
        if (i + 1 < 36)
            mat[i][i+1] = 1;
        mat[i][0] = (B >> i) & 1;
    }
    for (int t = 0; t < 18; ++t) {
        int mat2[36][36];
        memset(mat2, 0x00, sizeof(mat2));
        for (int i = 0; i < 36; ++i) {
            for (int j = 0; j < 36; ++j) {
                for (int k = 0; k < 36; ++k) {
                    mat2[i][j] ^= mat[i][k] * mat[k][j];
                }
            }
        }
        memcpy(mat, mat2, sizeof(mat));
    }

    vector<long long> B2(36);
    for (int i = 0; i < 36; ++i) {
        for (int j = 0; j < 36; ++j) {
            B2[i] += static_cast<long long>(mat[j][i]) << j;
        }
    }

    x = A;
    for (int i = 0; i < M; ++i) {
        if (offset.count(x)) {
           return offset[x] + static_cast<long long>(i) * M;
        }
        x = supernext(x, B2);
    }

    return -1;
}

int main() {
    long long A, B, X;
    cin >> A >> B >> X;
    cout << solve(A, B, X) << endl;
}

提出情報

ジャッジ結果