UTPC 2014 : K - 乱数調整

また知らないアルゴリズムが出た…。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_k

問題

乱数列aは整数A,Bから次のように定義される。

• 
• 

整数A,B,Xが与えられる。
となるTが存在するなら、その最小値を求めよ。
なお、A,B,Xは2^36未満である。

解法

Editorialを見て回答。

a[i]及びA,Bを36要素のbit vectorだと考える。
そうするとある36次正方行列Mを用いてとなる。

aは最大周期が2^36なので、愚直に1周試す時間はない。
しかしここでBaby-Step Giant-Stepアルゴリズムを適用できる。
元々このアルゴリズムは剰余環における整数の対数問題を解くためのものだが、ベクトル・行列にも同じ考え方が適用できる。

このアルゴリズムは例えば以下の解説がわかりやすい。
https://math.berkeley.edu/~sagrawal/su14_math55/notes_shank.pdf

これを用いると、周期Lの数列において、ある値のある位置をO(√L * logL)で求められる。

H=√Lとする。以下の2H個の項目を求めておく。

• X、MX、(M^2)X、,,,、(M^H)X
• A、(M^H)A、(M^2H)A、,,, 、(M^(H*H))A

後者(M^iH)Aを順次求めていき、その際前者のmapを用いていずれかと一致するものを求める。
ここで(M^j)X = (M^iH)Aの場合、X = (M^(iH-j))Aでありt=iH-jが候補となる。
あとは念のため X = (M^t)Aをチェックして答えればよい。

const int MAT=36;
struct Mat { int v[MAT][MAT]; };
Mat mulmat_gf2(Mat& a,Mat& b,int n=MAT) {
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) r.v[x][y] ^= a.v[x][z]&b.v[z][y];
	return r;
}

Mat powmat_gf2(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=x==y;
	while(p) {
		if(p%2) r=mulmat_gf2(r,a,n);
		a=mulmat_gf2(a,a,n);
		p>>=1;
	}
	return r;
}

ll A,B,X;
Mat BM,BMH;
ll BMH2[36];
map<ll,int> M;

ll getval(Mat m,ll v) {
	ll ret=0;
	int i,x;
	FOR(i,36) FOR(x,36) if(m.v[i][x] && (v&(1LL<<x))) ret ^= 1LL<<i;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>X;
	
	ll T=A;
	FOR(i,1<<18) {
		if(A==X) return _P("%d\n",i);
		A=(A/2)^(A%2*B);
	}
	if(B<1<<18) return _P("-1\n");
	
	ll X2=X;
	FOR(i,1<<18) {
		if(M.count(X2)==0) M[X2]=i;
		X2=(X2/2)^(X2%2*B);
	}
	
	FOR(i,35) BM.v[i][i+1]=1;
	FOR(i,36) BM.v[i][0]=(B>>i)&1;
	BMH=powmat_gf2(1<<18,BM);
	FOR(i,36) FOR(x,36) if(BMH.v[i][x]) BMH2[i] |= 1LL<<x;
	
	ll A2=A;
	FOR(i,1<<18) {
		if(M.count(A2)) {
			ll t=(1LL<<18)*i-M[A2];
			if(t>=0 && X==getval(powmat_gf2(t,BM),A)) return _P("%lld\n",t+(1<<18));
		}
		ll A3=0;
		FOR(x,36) A3 |= (__builtin_popcountll(BMH2[x]&A2)&1LL)<<x;
		A2=A3;
	}
	cout<<-1<<endl;
}

まとめ

Baby-Step Giant-Stepというアルゴリズム自体初耳だったので、こりゃ本番解けないわな。