MatrixPower

TCO11 Semifinal 1 · 2011-05-07 · by Smylic

TCO11 Semifinal 1 · 2011-05-07 · by Smylic · Math

Show categories

Class Name: MatrixPower

Return Type: int[]

Method Name: getElements

Arg Types: (int, int, int, int, vector<int>, vector<int>)

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.

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].

999997750
999801170
1304
90
{105,1256,12,781,634,1,139,1031,1032,1,110,8,562,1300,51,4,1294,995,225,1152,1236,304,1063,27,1289,1279,647,20,152,1291,19,783,1136,319}
{1301,1005,1,12,1190,1003,563,3,43,252,1230,1221,1301,445,1303,1291,88,8,5,34,1244,65,814,54,1300,1277,357,1256,639,1302,1291,1198,291,204}
Returns: {847030298, 771507297, 613518998, 77824623, 679390765, 488253441, 571177605, 207362171, 948701489, 750630538, 811872341, 221687412, 632740709, 574300913, 589072721, 901850687, 684667604, 942828693, 677856815, 318211344, 563503267, 118442359, 28956589, 570010751, 37993450, 825635916, 277347919, 629134920, 180756072, 656406739, 212954544, 789783930, 673872716, 609333041 }

999999757
25
13
2
{0,7,1,11,0,9,0,1,10,3,10,2,1,0,1,9,2}
{0,7,11,1,7,2,6,12,4,7,2,1,1,11,6,9,1}
Returns: {362460056, 485436053, 687895418, 369144167, 430807818, 190828199, 647035854, 335296911, 252668526, 168505631, 193671949, 326000417, 321206667, 243575299, 194885155, 687988413, 326000417 }

999999993
40
2
999907167
{0,1,0,1,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,1,0,0,0}
{0,1,0,0,0,1,1,1,1,0,1,1,0,1,0,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,0,0,0}
Returns: {895796656, 539456939, 895796656, 65296652, 895796656, 29856457, 29856457, 539456939, 539456939, 65296652, 29856457, 539456939, 895796656, 29856457, 895796656, 29856457, 895796656, 29856457, 65296652, 539456939, 29856457, 539456939, 895796656, 895796656, 539456939, 29856457, 895796656, 29856457, 65296652, 65296652, 539456939, 895796656, 895796656, 895796656 }

12
998445534
9621
3461169
{55,470,9620,9594,9500,9080}
{9613,7588,6537,0,2366,9441}
Returns: {393062141, 777646372, 569851897, 680954875, 136193723, 523187372 }

51)

0
1
10
3
{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.

52)

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.

Submissions are judged against all 123 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MatrixPower with a public method vector<int> getElements(int d, int q, int n, int k, vector<int> rows, vector<int> columns) · 123 test cases · 2 s / 256 MB per case