Submission #374193

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

i64 A, B, X;
int W;

struct matrix
{
	int val[36][36];
};

matrix calc_rev(matrix m)
{
	matrix ret;

	for (int i = 0; i < W; ++i) {
		for (int j = 0; j < W; ++j) {
			ret.val[i][j] = (i == j) ? 1 : 0;
		}
	}

	for (int i = 0; i < W; ++i) {
		if (m.val[i][i] != 1) {
			for (int j = i + 1; j < W; ++j) if (m.val[j][i] == 1) {
				for (int k = 0; k < W; ++k) {
					swap(m.val[j][k], m.val[i][k]);
					swap(ret.val[j][k], ret.val[i][k]);
				}
				goto nex;
			}
			fprintf(stderr, "><");
			exit(0);

		nex:
			i += 0;
		}

		for (int j = 0; j < W; ++j) if (i != j && m.val[j][i] == 1) {
			for (int k = 0; k < W; ++k) {
				m.val[j][k] ^= m.val[i][k];
				ret.val[j][k] ^= ret.val[i][k];
			}
		}
	}

	return ret;
}

matrix matmul(matrix a, matrix b)
{
	matrix ret;
	for (int i = 0; i < W; ++i) {
		for (int j = 0; j < W; ++j){
			ret.val[i][j] = 0;
			for (int k = 0; k < W; ++k) ret.val[i][j] ^= a.val[i][k] & b.val[k][j];
		}
	}
	return ret;
}

matrix matpow(matrix &m, int p)
{
	if (p == 1) return m;
	matrix tmp = matpow(m, p / 2);
	tmp = matmul(tmp, tmp);
	if (p % 2 == 1) tmp = matmul(tmp, m);
	return tmp;
}

i64 apply(matrix &m, i64 vec)
{
	i64 ret = 0;
	for (int i = 0; i < W; ++i) {
		int sig = 0;
		for (int j = 0; j < W; ++j) {
			sig ^= m.val[i][j] & (int)(vec >> (i64)j) & 1;
		}
		ret |= (i64)sig << (i64)i;
	}
	return ret;
}

void show(matrix &mat)
{
	for (int i = 0; i < W; ++i) {
		for (int j = 0; j < W; ++j) printf("%d ", mat.val[i][j]);
		puts("");
	}
	puts("");
}

int main()
{
	scanf("%lld%lld%lld", &A, &B, &X);
	int def = 50050;

	for (int i = 0; i < def; ++i) {
		if (A == X) {
			printf("%d\n", i);
			return 0;
		}
		A = (A / 2) ^ (A % 2 * B);
	}

	if (B == 0) {
		puts("-1");
		return 0;
	}

	W = 0;
	for (int i = 1; i <= 36; ++i) if ((1LL << (i64)i) > B) {
		W = i;
		break;
	}

	if ((1LL << (i64)W) <= X) {
		puts("-1");
		return 0;
	}

	matrix matr, rev, heavy;
	for (int i = 0; i < W; ++i) for (int j = 0; j < W; ++j) matr.val[i][j] = 0;
	for (int i = 0; i < W - 1; ++i) matr.val[i][i + 1] = 1;
	for (int i = 0; i < W; ++i) if ((1LL << (i64)i) & B) matr.val[i][0] = 1;

	heavy = matpow(matr, 1 << 18);
	rev = calc_rev(heavy);

	matrix mm = matmul(heavy, rev);
	//show(rev);
	//show(mm);

	map<i64, int> lval;
	i64 ret = 1LL << 60LL;

	for (int i = 0; i < (1 << 18); ++i) {
		if (lval.count(A) == 0) {
			lval.insert(make_pair(A, i));
		}
		A = apply(matr, A);
	}
	for (int i = 0; i < (1 << 18); ++i) {
		if (lval.count(X)) {
			ret = min(ret, (i64)i * (1 << 18) + lval[X]);
		}
		X = apply(rev, X);
	}

	if (ret > 1LL << 38LL) ret = -def - 1;
	printf("%lld\n", ret + def);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:107:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &A, &B, &X);
                                   ^

Judge Result