Submission #726855


Source Code Expand

class BitMatrix:
    __slots__ = ['n', 'mat', 'mask', 'u', 'v']
    def __init__(self, n):
        self.n = n
        self.mat = 0
        #self.mask = 2**(n**2) - 1
        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

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

Submission Info

Submission Time
Task D - 漸化式
User yaketake08
Language Python (2.7.3)
Score 100
Code Size 2832 Byte
Status AC
Exec Time 1547 ms
Memory 3632 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 17
Set Name Test Cases
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, small_1.txt, small_2.txt
Case Name Status Exec Time Memory
random_01.txt AC 64 ms 3616 KB
random_02.txt AC 66 ms 3632 KB
random_03.txt AC 57 ms 3496 KB
random_04.txt AC 59 ms 3504 KB
random_05.txt AC 59 ms 3504 KB
random_06.txt AC 61 ms 3628 KB
random_07.txt AC 147 ms 3620 KB
random_08.txt AC 314 ms 3620 KB
random_09.txt AC 1487 ms 3620 KB
random_10.txt AC 1547 ms 3616 KB
random_11.txt AC 1537 ms 3616 KB
random_12.txt AC 1538 ms 3504 KB
random_13.txt AC 1539 ms 3628 KB
random_14.txt AC 1535 ms 3616 KB
random_15.txt AC 1377 ms 3624 KB
sample_1.txt AC 59 ms 3628 KB
sample_2.txt AC 61 ms 3624 KB
sample_3.txt AC 97 ms 3620 KB
small_1.txt AC 62 ms 3632 KB
small_2.txt AC 64 ms 3632 KB