Submission #381809

---

Source Code Expand

//UTPC2014K 乱数調整
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint baby[(1<<18)+10],giant[(1<<18)+10];
map<lint,vector<vector<int> > > me;
map<lint,int> mi;
vector<int> cl(36,0);
vector<vector<int> > cal(lint a){
	if(me.count(a)>0) return me[a];
	vector<vector<int> > mae=cal(a/2),ato=cal(a-a/2),ret(36,cl);
	rep(i,36) rep(j,36) rep(k,36){
		ret[i][j]^=(mae[i][k]&ato[k][j]);
	}
	return me[a]=ret;
}
int main()
{
	lint A,B,X,now;int T=(1<<18);
	cin>>A>>B>>X;now=A;
	rep(i,(1<<18)+10){
		if(now==X){
			cout<<i<<endl;return 0;
		}
		//if(i==(1<<18)) cerr<<now<<endl;
		now=((now/2)^((now%2)*B));
	}
	baby[0]=X;giant[0]=A;mi[X]=0;
	rep(i,(1<<18)){
		baby[i+1]=baby[i]/2;
		if(baby[i]%2>0) baby[i+1]^=B;
		mi[baby[i+1]]=i+1;
	}
	vector<vector<int> > one(36,cl);
	rep(i,35) one[i][i+1]=1;
	rep(i,36){
		if(((1LL<<i)&B)) one[i][0]=1;
	}
	me[1]=one;
	vector<vector<int> > gi=cal((1<<18));
	rep(i,(1<<18)){
		giant[i+1]=0;
		rep(j,36){
			lint t=0;
			rep(k,36){
				if(((1LL<<k)&giant[i]) && gi[j][k]>0) t^=1;
			}
			giant[i+1]+=t<<j;
		}
	}
	//cerr<<giant[1]<<endl;
	lint ret=1145141919810893LL;
	REP(i,1,(1<<18)+1){
		if(mi.count(giant[i])<1) continue;
		lint t=i;t=(t<<18)-mi[giant[i]];
		ret=min(ret,t);
		//cout<<t<<endl;return 0;
	}
	if(ret>(1LL<<37)){cout<<-1<<endl;return 0;}
	now=giant[ret/T];
	rep(i,ret%T) now=((now/2)^((now%2)*B));
	if(now==X) cout<<ret<<endl;
	else cout<<-1<<endl;
}

Submission Info

Judge Result