[1/2]
import math
# 0 1 a c a a+c 1 1 a+c c 1 0
# 1 0 b d b b+d 0 1 b+d d 1 1
class Matrix:
I = [1, 0, 0, 1]
S = [0, 1, 1, 0]
L = [1, 1, 0, 1]
R = [1, 0, 1, 1]
@ staticmethod
def new ():
return [None] * 4
@ staticmethod
def copy (m):
return m [:]
@ staticmethod
def copyinto (msrc, mdst):
mdst [:] = msrc
@ staticmethod
def pair (m):
return (m [0] + m [1], m [2] + m [3])
@ staticmethod
def mul (m1, m2, mout):
mout [0] = m1 [0] * m2 [0] + m1 [1] * m2 [2]
mout [1] = m1 [0] * m2 [1] + m1 [1] * m2 [3]
mout [2] = m1 [2] * m2 [0] + m1 [3] * m2 [2]
mout [3] = m1 [2] * m2 [1] + m1 [3] * m2 [3]
class Stack:
@ staticmethod
def alloc (size, matrixclass):
new = matrixclass.new
return [new () for k in range (size)]
@ staticmethod
def ensure (stack, need, matrixclass):
have = len (stack)
if have < need:
stack.extend (Stack.alloc (need - have, matrixclass))
class Expo:
@ staticmethod
def bits (m, exp, mstack, stackpos, matrixclass):
MC = matrixclass
if exp < 1:
MC.copyinto (MC.I, mstack [stackpos])
return
if exp == 1:
MC.copyinto (m, mstack [stackpos])
return
outnow = stackpos
outother = stackpos + 1
powernow = stackpos + 2
powerother = stackpos + 3
div, mod = divmod (exp, 2)
left = div
mul = MC.mul
Stack.ensure (mstack, stackpos + 4, MC)
MC.copyinto (m, mstack [powernow])
MC.copyinto (m if mod else MC.I, mstack [outnow])
while left:
div, mod = divmod (left, 2)
left = div
mul (mstack [powernow], mstack [powernow], mstack [powerother])
powernow, powerother = powerother, powernow
if mod:
mul (mstack [outnow], mstack [powernow], mstack [outother])
outnow, outother = outother, outnow
if outnow != stackpos:
MC.copyinto (mstack [outnow], mstack [stackpos])
# context
# stack
# matrixclass
class Group:
@ classmethod
def kind (cls):
pass
def eval (self, ctx, stackpos):
pass
class EmptyGroup (Group):
@ classmethod
def kind (cls):
return "empty"
def eval (self, ctx, stackpos):
MC = ctx ["matrixclass"]
stack = ctx ["stack" ]
MC.copyinto (MC.I, stack [stackpos])
class FixedGroup (Group):
@ classmethod
def kind (cls):
return "fixed"
def __init__ (self, fixedstr):
self.fixedstr = fixedstr
def eval (self, ctx, stackpos):
MC = ctx ["matrixclass"]
stack = ctx ["stack" ]
fs = self.fixedstr
count = len (fs)
if count < 1:
MC.copyinto (MC.I, stack [stackpos])
return
sym = {'L': MC.L, 'R': MC.R}
if count == 1:
MC.copyinto (sym [fs], stack [stackpos])
return
div, mod = divmod (count - 1, 2)
if mod:
now = stackpos + 1
other = stackpos
else:
now = stackpos
other = stackpos + 1
Stack.ensure (stack, stackpos + 2, MC)
mnow = stack [now ]
mother = stack [other]
MC.copyinto (sym [fs [0]], mnow)
mul = MC.mul
fspos = 1
for k in range (div):
mul (mnow, sym [fs [fspos ]], mother)
mul (mother, sym [fs [fspos + 1]], mnow)
fspos += 2
if mod:
mul (mnow, sym [fs [fspos]], mother)