GCJ Qualification Round 2015 Problem C. Dijkstra

問題

i,j,kのみで構成されたL文字の文字列sをX個連結した文字列を適当に3つに分割して、
「分割した部分文字列の各要素を四元数として見て積をとると順にi,j,kとすることが出来るかどうか」
を判定する問題。
例えば、
L=2,X=6,s="ji"のとき、連結して出来た文字列は
jijijijijiji
であるが、これを
jij | iji | jijiji
と分割することによってそれぞれの積をとるとi,j,kになるので答えはYESとなる。

制限

テストケース数<=100

L<=10000
L*X<=10000(small)
L*X<=10^16(large) , X<=10^12(large)

解法(small)

以下の性質を利用する。
・a,b,cが四元数のとき(a*b)*c=a*(b*c) (四元数の結合則)
連結して出来た文字列をtとしたとき、
t = ○ | △ | □
と分割してそれぞれの積が順にi,j,kとなっているならば
○*△=(○の積)*(△の積)=i*j=k
○*△*□ = (○*△)*(□の積) = k*k = -1
となるはず.
よって、連結して出来た文字列を順に掛けて行って途中でi,kが出てかつ全部掛けたら-1になっていれば良いのでO(L*X)で出来る。

解法(large)

以下の性質を利用する。
・四元数の要素である1,-1,i,-i,j,-j,k,-kはどれも4乗すると1になる。
sをX個連結した後に3分割するので、各分割の中にはsがそれぞれ幾つか含まれていなければならない。その個数をそれぞれa,b,cとする。また、sの文字を全て掛けたものをhとおく。この時、
・最初の分割の積=h^a * (sの途中までの積) = i
・真ん中の分割の積=h^b * (sの途中から別のsの途中までの積) = j
・最後の分割の積=h^c * (sの途中からsの最後までの積) = k
みたいな感じになる(厳密にはa+b+c=X-2やa+b+c=X-1の場合等がありえる)
そしてh^4=1なので、a,b,cは4で剰余をとってよかったりする。
そう考えると考えるべき状態数は
a,b,cが0,1,2,3のそれぞれの場合について考えれば良いのだから、
X = min(X, 12+X%12)
として良い。こうするとX<24だから十分間に合う。