まわり将棋に挑戦！

まず、金将の状態を列挙し、取りうる和の集合を求める。その集合の要素を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)で求解することができた。

Ruby https://github.com/cielavenir/codeiq_solutions/blob/master/thisweek_masuipeo2/tyama_codeiq2900.rb
Python(2/3) https://github.com/cielavenir/codeiq_solutions/blob/master/thisweek_masuipeo2/tyama_codeiq2900.py