Submission #7803795

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
import numpy as np
K,M = map(int,readline().split())
A = np.array(readline().split(),np.int64)
C = np.array(readline().split(),np.int64)
A,C
K
mask = (1<<32)-1
mat = np.eye(K,K,-1,np.int64) * mask
mat[0] = C
def mat_prod(A,B):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

K,M = map(int,readline().split())
A = np.array(readline().split(),np.int64)
C = np.array(readline().split(),np.int64)

A,C

K

mask = (1<<32)-1
mat = np.eye(K,K,-1,np.int64) * mask
mat[0] = C

def mat_prod(A,B):
    a,b = A.shape
    c,d = B.shape
    assert b == c
    return np.bitwise_xor.reduce(A[:,:,None] & B[None,:,:],axis=1)

def mat_power(A,N):
    if N == 0:
        return np.eye(K,dtype=np.int64) * mask
    mat = mat_power(A,N//2)
    mat = mat_prod(mat,mat)
    return mat_prod(mat,A) if N&1 else mat

x = mat_power(mat,M-1)
v = mat_prod(x,A[::-1].reshape(-1,1))
answer = v[-1,0]
print(answer)

Submission Info

Judge Result