# A little optimization from the naive idea got AC slow though.

1. Based on the definition of vector multiplication, this piece of solution comes out:
``````class Solution(object):
def multiply(self, A, B):
# brute force TLE
aw, ah, bw, bh, answ, ansh = len(A[0]), len(A), len(B[0]), len(B), len(B[0]), len(A)
answer = [ [0 for i in xrange(answ)] for j in xrange(ansh) ]
for i in xrange(ansh):
for j in xrange(answ):
ansij = 0
for x in xrange(aw):
ansij += A[i][x] * B[x][j]
``````

2.I notice it failed out of TLE when there are too many zeros during the calculation. So this time I preprocess A and B using a binary number where 1 and 0 represent nonzero and zero respectively.
Then A & B shows us which element should be count which shouldn't.

``````class Solution(object):
def multiply(self, A, B):
#using bitwise operation to minimize the number of calculation
aw, ah, bw, bh, answ, ansh = len(A[0]), len(A), len(B[0]), len(B), len(B[0]), len(A)
MA, MB = [0 for i in xrange(ah)], [0 for i in xrange(bw)]
for i in xrange(ah):
ta = 0
for j in xrange(aw):
ta <<= 1
ta += 0 if A[i][j] == 0 else 1
MA[i] = ta
for i in xrange(bw):
tb = 0
for j in xrange(bh):
tb <<= 1
tb += 0 if B[j][i] == 0 else 1
MB[i] = tb
answer = [ [0 for i in xrange(answ)] for j in xrange(ansh) ]
for i in xrange(ansh):
for j in xrange(answ):
ansij, idxs = 0, MA[i] & MB[j]
idx = aw - 1
while idxs:
if idxs % 2:
ansij += A[i][idx] * B[idx][j]
idx, idxs = idx - 1, idxs >> 1