Tribonacci | Topcoder Archive

Problem Statement

You are given the following data:

ints a, b, c, d, e, and f: positive integer coefficients.
longs n and m: upper bounds for a sum and a product.
int[] mat: the elements of a K*K matrix (in row-major order)

Let T(p) denote the p-th power of the matrix described by mat.

We can now define a new K*K matrix as follows:

Find this matrix. Compute and return the sum of all its elements, modulo 2,147,483,648 . Note that the product is inside the sum.

Definition

Class:: Tribonacci
Method:: findValue
Parameters:: int, int, int, int, int, int, long, long, int[]
Returns:: int
Method signature:: int findValue(int a, int b, int c, int d, int e, int f, long n, long m, int[] mat)
(be sure your method is public)

Notes

The value of K is not given explicitly, because it's uniquely determined by mat.

Constraints

Each of the numbers a, b, c, d, e, and f will be between 1 and 10^9, inclusive.
n will be between 1 and 10^18, inclusive.
m will be between 1 and 10^18, inclusive.
K will be between 1 and 50, inclusive.
mat will contain exactly K elements, and each element of mat will contain exactly K values.
Each number in mat will be between 1 and 10^9, inclusive.

Examples

{6497,3829,9936,4347,7683,7241,6576,794,5869,4953,8425,2751,5955,1548,7760,1699,9844,4877,9838,3947,8546,533,3076,656,1227,593,2770,7983,8993,2311,621,1842,2492,558,6190,176,4151,2766,970,6372,7720,9395,5475,27,7296,3236,1726,3492,4465,7916,7439,3011,4801,516,3668,6029,7461,2790,364,2806,5101,986,4649,3945,7896,839,473,8399,3605,1443,4772,7677,7191,247,7705,839,9835,5783,4331,4300,52,1770,3664,4853,8638,3684,7234,2451,6474,7599,5258,7927,8585,9907,8224,2833,7098,8698,1232,703,6493,6004,4733,36,2604,8790,875,2439,4573,1558,3092,4625,9681,3108,5831,8319,6792,3065,771,9618,7016,2381,3897,1953,2288,2121,4786,9386,7171,6019,6441,3665,8375,1174,53,979,9964,929,9771,890,8839,9215,1867,8520,2323,4050,3192,5467,3468,315,1437,484,2696,5334,2438,1336,3807,3576,7074,979,5947,9867,996,4323,1042,1049,1654,7358,1978,1425,4600,7170,6992,6468,5690,9315,6870,8882,1134,338,9197,2571,823,8245,7905,9613,9581,1713,3189,6655,9044,9137,6523,40,9812,3917,1089,1466,7627,9420,2892,2228,6590,9884,5048,8632,5552,1918,7515,6686,2257,3064,5610,9432,1310,9867,9045,891,7932,8586,3899,6976,4075,422,3368,3887,691,4458,1706,8318,230,950,6898,3172,834,8298,1804,2738,217,9319,5777,8826,8736,1387,8258,46,1254,3655,937,9187,8593,1188,2515,9021,7962,5884}

Returns: 1072237232

```
1
```
```
1
```
```
1
```
```
1
```
```
1
```
```
1
```
```
2
```
```
2
```
```
{3}
```
```
Returns: 118341
```
The Matrix consists of a single element only. The expression evaluates to 118341.

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.