Coding questions · WeRide

Implement matrix multiplication and fast exponentiation

This question evaluates competency in matrix multiplication, modular arithmetic, and exponentiation algorithms as applied to large-scale numeric computations such as sequence generation.

1)

A n × m
B m × p

C = A × B``n × p

MOD MOD

2) Exponentiation by Squaring

x k MOD

x^k
x^k mod MOD
O(log k)
k = 0``x = 0

3)

n (n ≥ 0) n F(n)

F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2)
2×2 O(log n)
MOD

/

multiply(A, B) -> C
pow(x, k, MOD=None) -> value
fib(n, MOD=None) -> value

n 10^9 DP

Matrix Multiplication

Return A times B, optionally modulo MOD.

Examples

Example 1

Input: ([[1,2],[3,4]], [[5,6],[7,8]], None)
Output: [[19, 22], [43, 50]]

Explanation: Basic matrix multiplication.

Example 2

Input: ([[2]], [[5]], 7)
Output: [[3]]

Explanation: Modulo is applied if provided.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.

Exponentiation By Squaring

Return x^k, optionally modulo MOD.

Examples

Example 1

Input: (2,10,None)
Output: 1024

Explanation: 2^10.

Example 2

Input: (2,10,1000)
Output: 24

Explanation: Modulo exponentiation.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.

Fast Fibonacci With Matrix Power

Return F(n), optionally modulo MOD, using 2x2 matrix exponentiation.

Examples

Example 1

Input: (10,None)
Output: 55

Explanation: F(10)=55.

Example 2

Input: (100,1000)
Output: 75

Explanation: Modulo Fibonacci.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.