ビット行列の計算をPythonでするよ

BitMatrix.py

# -*- encoding: utf-8 -*-
# 以下を参考にさせていただきました
# http://anond.hatelabo.jp/20151220172711
class BitMatrix:
    def __init__(self, n=0, m=0, l=8):
        self.n = n; self.m = m
        self.mat = [[0] * ((m+l-1)/l) for i in xrange((n+l-1)/l)]
        self.l = l
        self.mask = 2**(l**2)-1
        self.nr = range((n+l-1)/l)
        self.mr = range((m+l-1)/l)

        self.u = u = 2**l - 1
        # Sn = (h^n - 1) / (h-1) where h = 2**l
        self.v = ((u+1)**l - 1) / u
    def copy(self, other):
        self.n = other.n; self.m = other.m
        self.mat = [e[:] for e in other.mat]
        self.l = other.l
        self.mask = other.mask
        self.nr = other.nr
        self.mr = other.mr
        self.u = other.u; self.v = other.v
        return self

    def set(self, i, j, b):
        l = self.l
        bit = 1 << ((i%l)*l + (j%l))
        self.mat[i/l][j/l] &= self.mask ^ bit
        if b:
            self.mat[i/l][j/l] |= bit
        return self
    def setI(self):
        assert self.n == self.m
        l = self.l
        # (2^{l(l+1)}-1) / (2^(l+1)-1)
        # l=8 -> 0x8040201008040201
        value = (2**((l+1)*l)-1) / (2**(l+1)-1)
        for i in self.nr:
            self.mat[i][i] = value
        return self
    def get(self, i, j):
        l = self.l
        return (self.mat[i/l][j/l] >> ((i%l)*l + (j%l))) & 1
    def __add__(self, other):
        assert self.n == other.n and self.m == other.m
        res = BitMatrix(self.n, self.m, self.l)
        me = self.mat; you = other.mat
        nr = self.nr; mr = self.mr
        for i in nr:
            for j in mr:
                res[i][j] = me[i][j] | you[i][j]
        return res
    def __mul__(self, other):
        assert self.l == other.l
        u = self.u; v = self.v; l = self.l
        def mul(a, b):
            c = 0
            while a and b:
                # 演算xor
                c ^= (((a & v) * u) & ((b & u) * v))
                a >>= 1; b >>= l
            return c
        res = BitMatrix(self.n, other.m, self.l)
        me = self.mat; you = other.mat
        nr = self.nr
        nro = other.nr; mro = other.mr
        for i in nr:
            for k in nro:
                for j in mro:
                    # 演算xor
                    res.mat[i][j] ^= mul(me[i][k], you[k][j])
        return res
    def __pow__(self, k):
        assert self.n == self.m
        res = BitMatrix(self.n, self.n, self.l).setI()
        me = BitMatrix().copy(self)
        while k:
            if k&1:
                res = res * me
            me = me * me
            k >>= 1
        return res

# AtCoder ABC009 - D問題
# lの値(配列の要素に保持する行列ビットサイズ[サイズl*l])
#   8(TLE): http://abc009.contest.atcoder.jp/submissions/726799
#  32(TLE): http://abc009.contest.atcoder.jp/submissions/726805
#  64(TLE): http://abc009.contest.atcoder.jp/submissions/726807
#  99(TLE): http://abc009.contest.atcoder.jp/submissions/726812
# 100(AC) : http://abc009.contest.atcoder.jp/submissions/726810
k, m = map(int, raw_input().split())
a = map(int, raw_input().split())
c = map(int, raw_input().split())
if m <= k:
    print a[m-1]
else:
    ans = 0
    # 32bitを1bitごとにビット行列演算
    for b in xrange(32):
        mat = BitMatrix(k, k, 100)
        bit = 1 << b
        for i in xrange(k):
            if c[i] & bit:
                mat.set(0, i, 1)
        for i in xrange(k-1):
            mat.set(i+1, i, 1)
        res = mat ** (m - k)
        d = 0
        for i in xrange(k):
            if a[i] & bit:
                d ^= res.get(0, k-i-1)
        if d:
            ans |= bit
    print ans

BitMatrix2.py

# encoding: utf-8
# 配列なしで全て同じ数値のビット中で計算したもの
class BitMatrix:
    __slots__ = ['n', 'mat', 'mask', 'u', 'v']
    def __init__(self, n):
        self.n = n
        self.mat = 0
        self.u = u = 2**n - 1
        self.v = ((u+1)**n - 1) / u
    def copy(self, other):
        #assert self.n == other.n
        self.mat = other.mat
        return self

    def set(self, i, j, b):
        bit = 1 << (i*self.n + j)
        if b:
            self.mat |= bit
        else:
            self.mat &= ~bit
        return self
    def setZ(self):
        self.mat = 0
        return self
    def setI(self):
        n = self.n
        self.mat = (2**((n+1)*n) - 1) / (2**(n+1) - 1)
        return self
    def get(self, i, j):
        return (self.mat >> (i*self.n + j)) & 1
    def __add__(self, other):
        #assert self.n == other.n
        res = BitMatrix(self.n)
        res.mat = self.mat ^ other.mat
        return res
    def __iadd__(self, other):
        #assert self.n == other.n
        n = self.n
        self.mat ^= other.mat
        return self
    def __mul__(self, other):
        #assert self.n == other.n
        n = self.n; u = self.u; v = self.v
        res = BitMatrix(n)
        c = 0; a = self.mat; b = other.mat
        while a and b:
            c ^= ((a & v) * u) & ((b & u) * v)
            a >>= 1; b >>= n
        res.mat = c
        return res
    def __imul__(self, other):
        #assert self.n == other.n
        n = self.n; u = self.u; v = self.v
        c = 0; a = self.mat; b = other.mat
        while a and b:
            c ^= ((a & v) * u) & ((b & u) * v)
            a >>= 1; b >>= n
        self.mat = c
        return self
    def __pow__(self, k):
        res = BitMatrix(self.n).setI()
        A = BitMatrix(self.n).copy(self)
        while k:
            if k&1:
                res *= A
            A *= A
            k >>= 1
        return res
    def __ipow__(self, k):
        if k == 0:
            return self.setI()
        A = BitMatrix(self.n).copy(self)
        k -= 1
        while k:
            if k&1:
                self *= A
            A *= A
            k >>= 1
        return self

# AtCoder, ABC009 - D (AC)
# http://abc009.contest.atcoder.jp/submissions/726855
k, m = map(int, raw_input().split())
a = map(int, raw_input().split())
c = map(int, raw_input().split())
if m <= k:
    print a[m-1]
else:
    ans = 0
    bit = 1
    mat = BitMatrix(k)
    for i in xrange(k-1):
        mat.set(i+1, i, 1)
    temp = mat.mat
    for b in xrange(32):
        mat.mat = temp
        for i in xrange(k):
            if c[i] & bit:
                mat.set(0, i, 1)
        mat **= m - k
        d = 0
        for i in xrange(k):
            if a[i] & bit:
                d ^= mat.get(0, k-i-1)
        if d:
            ans |= bit
        bit <<= 1
    print ans