Submission #1050143


Source Code Expand

k, m = map(int, raw_input().split())
A = map(int, raw_input().split())
Ck = map(int, raw_input().split())[::-1]

def nxt(C):
    C1 = [0]*k
    C1[0] = C[k-1] & Ck[0]
    for i in xrange(1, k):
        C1[i] = C[i-1] ^ (C[k-1] & Ck[i])
    return C1
def dbl(C):
    Ci = C[:]
    C1 = [0]*k
    for j in xrange(k):
        for i in xrange(k):
            C1[i] ^= C[j] & Ci[i]
        Ci = nxt(Ci)
    return C1

def solve(m):
    if m <= k:
        return A[m-1]
    def dfs(m):
        if m < k:
            C = [0]*k
            C[m] = 2**32 - 1
            return C
        C = dbl(dfs(m / 2))
        if m % 2 == 1:
            C = nxt(C)
        return C
    C = dfs(m-1)
    res = 0
    for i in xrange(k):
        res ^= C[i] & A[i]
    return res
print solve(m)

Submission Info

Submission Time
Task D - 漸化式
User yaketake08
Language Python (2.7.3)
Score 100
Code Size 806 Byte
Status AC
Exec Time 106 ms
Memory 3572 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 40 ms 3536 KB
random_02.txt AC 40 ms 3572 KB
random_03.txt AC 39 ms 3440 KB
random_04.txt AC 39 ms 3440 KB
random_05.txt AC 39 ms 3440 KB
random_06.txt AC 40 ms 3452 KB
random_07.txt AC 47 ms 3488 KB
random_08.txt AC 58 ms 3456 KB
random_09.txt AC 104 ms 3488 KB
random_10.txt AC 103 ms 3492 KB
random_11.txt AC 105 ms 3452 KB
random_12.txt AC 105 ms 3452 KB
random_13.txt AC 105 ms 3452 KB
random_14.txt AC 106 ms 3568 KB
random_15.txt AC 103 ms 3572 KB
sample_1.txt AC 40 ms 3572 KB
sample_2.txt AC 39 ms 3452 KB
sample_3.txt AC 44 ms 3452 KB
small_1.txt AC 39 ms 3452 KB
small_2.txt AC 38 ms 3448 KB