Controllo rapido Matrix Moltiplicazione in Mod 10

Question

Di recente ho affrontato questo problema in un concorso di programmazione: dato 3 matrici quadrate n x n di dimensioni n fino a 1000. Tutti gli elementi in 3 matrici sono da 0 a 9. Controlla se Matrix A X B è uguale a C, Mod 10. parole, restituire il risultato dell'espressione (A x B) mod 10 == C.

Per esempio:

$ qquad a = inizio {bmatrix} 0 & 5 & 8 1 & 4 & 9 2 & 3 & 3 end {bmatrix} qquad b = inizio {bmatrix} 3 & 5 & 0 1. $

Ritorno: vero

Se

$ qquad c = inizio {bmatrix} 1 & 6 & 0 4 & 6 & 4 8 & 7 & 8 end {bmatrix} $

Ritorno: falso, poiché l'elemento C (1, 1) deve essere 9.

Il limite di tempo è 1s, piuttosto severo. Per favore mi dà un'idea di come risolvere il problema in modo efficiente; È possibile che $ O (n^2) $?