クロッシング・ワード

codeiq_cword.rb

# https://codeiq.jp/q/2841
# 
# 方針:(n>=2)
# 
# 各列のパターンは次の5つのいずれか．
# 0.___ 1.#__ 2._#_ 3.__# 4.#_#
# 
# i列目にそのパターンが配置できるかどうか判定するには，i-1,i-2列目の情報が必要．
# 愚直に再帰を使って実装すると，gchokuメソッドのようになる．TLE．
#
# i-1,i-2列目の情報さえあれば，i行目でどうなるか分かるので
# 行列を使って遷移表を作り，二分累乗法で解く．
# 

def scan; gets.split.map(&:to_i); end
    
require 'matrix'

F___ = 0
FW__ = 1
F_W_ = 2
F__W = 3
FW_W = 4
FXXX = 5

MI___t___ = 0
MI___tW__ = 1
MI___t_W_ = 2
MI___t__W = 3
MI___tW_W = 4
MIW__t___ = 5
MIW__t_W_ = 6
MIW__t__W = 7
MI_W_t___ = 8
MI_W_tW__ = 9
MI_W_t__W = 10
MI__Wt___ = 11
MI__WtW__ = 12
MI__Wt_W_ = 13
MIW_Wt___ = 14


# 愚直
# n==1のケースはF_W_で分断されるので場合分けが必要
def gchoku(left, field2 = FXXX, field1 = FXXX)
    return (field1 == F_W_ && (field2 == FW__ || field2 == F__W)) ? 0 : 1 if (left == 0)
    
    result = 0
    result += gchoku(left - 1, field1, F___)
    result += gchoku(left - 1, field1, FW__) if (field1 == F___ || (field1 == F__W) || (field1 == F_W_ && field2 == F___) || field1 == FXXX)
    result += gchoku(left - 1, field1, F__W) if (field1 == F___ || (field1 == FW__) || (field1 == F_W_ && field2 == F___) || field1 == FXXX)
    result += gchoku(left - 1, field1, F_W_)if (field1 == F___ || field1 == FW__ || field1 == F__W || field1 == FXXX)
    result += gchoku(left - 1, field1, FW_W)if (field1 == F___ || field1 == FXXX)
    return result % 1000000;
end


mat = Matrix[[1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,1,1,1,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,1,1,1,0,0,0,0],
             [0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],
             [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
             [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],
             [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,1,1,1,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],
             [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,1,1,1,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
             [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],].transpose

n = gets.to_i

if n == 1
    p 4
elsif n == 2
    p 11
else
    # p gchoku(n)
    
    pow = n-2
    
    y = Vector[1,1,1,1,1,1,1,1,1,0,0,1,1,1,1]
    # y[MI_W_tW__] = 0
    # y[MI_W_t__W] = 0
    
    # (mat**pow)*y を求めたい．
    p_mat = Matrix.scalar(15,1)
    while (0<pow)
        p_mat  =mat*p_mat if pow%2==1
        mat=mat*mat
        pow/=2
        mat   =mat  .map{|e|e%1000000}
        p_mat =p_mat.map{|e|e%1000000}
    end
    y = (p_mat*y).map{|e|e%1000000}
    
    p (y.to_a.inject(:+) - (y[MIW__t_W_] + y[MI__Wt_W_]) + 2000000)%1000000
end