Submission #175602

---

Source Code Expand

from copy import deepcopy
k, m = map(int, raw_input().split())
a = map(int, raw_input().split())
c = map(int, raw_input().split())
mat = [[0 for i in xrange(k)] for j in xrange(k)]
# [ C1 C2 ... C(K-1) CK ]
# [  1  0 ...    0    0 ]
# [  0  1 ...    0    0 ]
# [  :  :        :    : ]
# [  0  0 ...    1    0 ]
#
# ( 1 <- (FFFFFFFF)_16 )
for i in xrange(k):
    mat[0][i] = c[i]
for i in xrange(k-1):
    mat[i+1][i] = int("FFFFFFFF", 16)
# identify matrix ( 1 <- (FFFFFFFF)_16 )
mat_a = [[int("FFFFFFFF", 16) if i==j else 0 for i in xrange(k)] for j in xrange(k)]

if m<=k:
    print a[m-1]
else:
    m -= k
    mat_d = [[0 for i in xrange(k)] for j in xrange(k)]
    mat2 = [[0 for i in xrange(k)] for j in xrange(k)]
    while m>0:
        if m%2==1:
            for i in xrange(k):
                for j in xrange(k):
                    mat_d[i][j] = 0
                    for l in xrange(k):
                        mat_d[i][j] ^= (mat_a[i][l] & mat[l][j])
            mat_a = deepcopy(mat_d)
        for i in xrange(k):
            for j in xrange(k):
                mat2[i][j] = 0
                for l in xrange(k):
                    mat2[i][j] ^= (mat[i][l] & mat[l][j])
        mat = deepcopy(mat2)
        m /= 2
    ans = 0
    for i in xrange(k):
        ans ^= (mat_a[0][i] & a[k-i-1])
    print ans

Submission Info

Judge Result