MatrixPower | Topcoder Archive

Problem Statement

NOTE: This problem statement contains subscripts/superscripts that may not display properly if viewed outside of the applet.

Raising a matrix to a power efficiently is a well known problem in computer science. Let A be matrix with elements a_ij where: 0 <= i,j < n. The value of each element is given by:
a_ij = d*i + q^j
Let B be the resulting matrix from raising A to the k-th power: B = A^k.
B has elements b_ij. You are to return some specific elements from B. The parameters rows and columns specify which elements. Element t of your return should contain the value of b_ij where i = rows[t] and j = columns[t].

You are given ints d, q, n, k and int[]s rows and columns. Return an int[] containing the values of some elements, b_ij, modulo 1,000,000,007.

Definition

Class:: MatrixPower
Method:: getElements
Parameters:: int, int, int, int, int[], int[]
Returns:: int[]
Method signature:: int[] getElements(int d, int q, int n, int k, int[] rows, int[] columns)
(be sure your method is public)

Constraints

d will be between 0 and 10^9, inclusive.
q will be between 1 and 10^9, inclusive.
n will be between 1 and 10,000, inclusive.
k will be between 1 and 10^9, inclusive.
rows will contain between 1 and 50 elements, inclusive.
columns will contain the same number of elements as rows.
Each element of rows will be between 0 and n-1, inclusive.
Each element of columns will be between 0 and n-1, inclusive.

Examples

```
1
```
```
2
```
```
2
```
```
2
```
```
{0,0,1,1}
```
```
{0,1,0,1}
```
```
Returns: {5, 8, 8, 13 }
```
A contains rows [1, 2] and [2, 3]. Then B = A2 contains rows [1*1+2*2, 1*2+2*3] = [5, 8] and [2*1+3*2, 2*2+3*3] = [8, 13].

{0,1,2,3,4,5,6,7,8,9}

{0,1,2,3,4,5,6,7,8,9}

Returns: {100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

A is a 10x10 matrix containing only 1s. A2 contains only 10s and B = A3 contains only 100s.

```
0
```
```
1000000000
```
```
1
```
```
1000000000
```
```
{0,0,0}
```
```
{0,0,0}
```
```
Returns: {1, 1, 1 }
```
You may be asked to return the value of the same element more the once.

1000000000

1000000000

1000000000

{0}

{0}

Returns: {380113608 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.