More than 5 years have passed since last update.

まわり将棋に挑戦！

Posted at 2016-08-03

まず、金将の状態を列挙し、取りうる和の集合を求める。その集合の要素を8で割ったあまりに振り分ける。

T=[0,1,5,10,20]
M=8

h={}
T.repeated_permutation(4){|a|h[a.reduce(:+)]=1}
a=[0]*M
h.each_key{|k|a[k%M]+=1}

2回金将を振った時、駒が角に動く場合は、(1回めに角、2回めに角)+(1回めにあまり1、2回めにあまり7)+...+(1回めに7、2回めにあまり1)通りである。
これは以下のように乗算として定義できる。

def mul(a,b)
	raise if a.size!=b.size
	r=[0]*a.size
	a.size.times{|i|
		b.size.times{|j|
			r[(i+j)%a.size]+=a[i]*b[j]
		}
	}
	r
end

乗算として定義できれば、繰り返し二乗法を適用することができる。

e=[1]+[0]*(M-1)
n=gets.to_i
while n>0
	e=mul(e,a) if n%2>0
	a=mul(a,a)
	n/=2
end
p e[0]

以上により、(多倍長計算を考えなければ)計算量O(logN)で求解することができた。