Submission #463934

---

Source Code Expand

declare -r M=10007

read n
((--n))

declare -a x=(0 1 0 0 0 1 1 1 1)
declare -a y=(1 0 0 0 1 0 0 0 1)

while (( n > 0 )) ; do
    if (( (n & 1) == 1 )) ; then
        y=( $(( (y[0]*x[0] + y[1]*x[3] + y[2]*x[6]) % M ))
            $(( (y[0]*x[1] + y[1]*x[4] + y[2]*x[7]) % M ))
            $(( (y[0]*x[2] + y[1]*x[5] + y[2]*x[8]) % M ))
            $(( (y[3]*x[0] + y[4]*x[3] + y[5]*x[6]) % M ))
            $(( (y[3]*x[1] + y[4]*x[4] + y[5]*x[7]) % M ))
            $(( (y[3]*x[2] + y[4]*x[5] + y[5]*x[8]) % M ))
            $(( (y[6]*x[0] + y[7]*x[3] + y[8]*x[6]) % M ))
            $(( (y[6]*x[1] + y[7]*x[4] + y[8]*x[7]) % M ))
            $(( (y[6]*x[2] + y[7]*x[5] + y[8]*x[8]) % M )) )
    fi

    n=$(( n >> 1 ))

    if (( n > 0 )) ; then
        x=( $(( (x[0]*x[0] + x[1]*x[3] + x[2]*x[6]) % M ))
            $(( (x[0]*x[1] + x[1]*x[4] + x[2]*x[7]) % M ))
            $(( (x[0]*x[2] + x[1]*x[5] + x[2]*x[8]) % M ))
            $(( (x[3]*x[0] + x[4]*x[3] + x[5]*x[6]) % M ))
            $(( (x[3]*x[1] + x[4]*x[4] + x[5]*x[7]) % M ))
            $(( (x[3]*x[2] + x[4]*x[5] + x[5]*x[8]) % M ))
            $(( (x[6]*x[0] + x[7]*x[3] + x[8]*x[6]) % M ))
            $(( (x[6]*x[1] + x[7]*x[4] + x[8]*x[7]) % M ))
            $(( (x[6]*x[2] + x[7]*x[5] + x[8]*x[8]) % M )) )
    fi
done

echo ${y[2]}

Submission Info

Judge Result