A Grouping Problem#1525

A Grouping Problem (Editorial)

Let $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n be a given set of $n$ integers. Denote by $F_{ik} (i \geq k)$ F_{ik}~(i \ge k) the sum of all possible products of $k$ integers chosen from the first $i$ integers $a_{1}, ..., a_{i}$ a_1, ..., a_i. Let us construct the following table of $F_{ik}$ F_{ik} values:

For four numbers, we obtain:

$F_{4, 1} = a_{1} + a_{2} + a_{3} + a_{4}$ F_{4,1} = a_1 + a_2 + a_3 + a_4;
$F_{4, 2} = a_{1} a_{2} + a_{1} a_{3} + a_{1} a_{4} + a_{2} a_{3} + a_{2} a_{4} + a_{3} a_{4}$ F_{4,2} = a_1a_2 + a_1a_3 + a_1a_4 + a_2a_3 + a_2a_4 + a_3a_4;
$F_{4, 3} = a_{1} a_{2} a_{3} + a_{1} a_{2} a_{4} + a_{1} a_{3} a_{4} + a_{2} a_{3} a_{4}$ F_{4,3} = a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4;
$F_{4, 4} = a_{1} a_{2} a_{3} a_{4}$ F_{4,4} = a_1a_2a_3a_4;

The following recurrence relations hold:

F_{i 1} = F_{(i - 1) 1} + a_{i} F_{ii} = F_{(i - 1) (i - 1)} \cdot a_{i}, 1 \leq i \leq n F_{ik} = F_{(i - 1) k} + F_{(i - 1) (k - 1)} \cdot a_{i}, 1 \leq i \leq n, 1 < k < i

F_{i1} = F_{(i-1)1} + a_i\\ F_{ii} = F_{(i-1) (i-1)} \cdot a_i, 1 \le i \le n \\ F_{ik} = F_{(i-1)k} + F_{(i-1) (k-1)} \cdot a_i, 1 \le i \le n, 1 < k < i

For example,

$F_{3, 2} = F_{2, 2} + F_{2,} 1 \cdot a_{3} = a_{1} a_{2} + (a_{1} + a_{2}) \cdot a_{3} = a_{1} a_{2} + a_{1} a_{3} + a_{2} a_{3}$ F_{3,2} = F_{2,2} + F_{2,}1 \cdot a_3 = a_1a_2 + (a_1 + a_2) \cdot a_3 = a_1a_2 + a_1a_3 + a_2a_3;
$F_{4, 3} = F_{3, 3} + F_{3, 2} \cdot a_{4} = a_{1} a_{2} a_{3} + (a_{1} a_{2} + a_{1} a_{3} + a_{2} a_{3}) \cdot a_{4} =$ F_{4,3} = F_{3,3} + F_{3,2} \cdot a_4 = a_1a_2a_3 + (a_1a_2 + a_1a_3 + a_2a_3) \cdot a_4 =
$a_{1} a_{2} a_{3} + a_{1} a_{2} a_{4} + a_{1} a_{3} a_{4} + a_{2} a_{3} a_{4}$
a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4

The values of each subsequent row are computed based on the values of the previous row, so it is sufficient to store a single linear array $d$ of size up to $1000$ . The recalculation of the $i$ -th row should be performed from the end: first compute $F_{ii}$ F_{ii}, then $F_{i (i - 1)}$ F_{i(i-1)}, and so on down to $F_{i 1}$ F_{i1}. All computations must be performed modulo $m$ .

Example

Consider the first test case. We'll construct two tables: in the first table, computations are performed without the modulo, and in the second table, computations are performed modulo $m = 10$ m = 10.

For example,

$F_{4, 2} = F_{3, 2} + F_{3, 1} \cdot 4 = 11 + 6 \cdot 4 = 35$ F_{4,2} = F_{3,2} + F_{3,1} \cdot 4 = 11 + 6 \cdot 4 = 35;
$F_{4, 3} = F_{3, 3} + F_{3, 2} \cdot 4 = 6 + 11 \cdot 4 = 50$ F_{4,3} = F_{3,3} + F_{3,2} \cdot 4 = 6 + 11 \cdot 4 = 50;

The answer is the maximum value in the fourth row of the second table.

Algorithm implementation

Declare a linear array $d$ , where the values of $F_{ik}$ F_{ik} will be recomputed.

long long d[1000];

Read the number of elements $n$ and the value $m$ . For each input test case, the array $d$ is initially cleared. The first number $a_{1}$ a_1 is stored in $d [0]$ .

while (scanf("%lld %lld",&n,&m), n + m > 0)
{
  memset(d,0,sizeof(d));
  scanf("%lld",&d[0]);

Next, read the value $x = a_{i + 1} (1 \leq i < n)$ x = a_{i+1}~(1 \le i < n) and recalculate the values of $F_{ik}$ F_{ik} for $k = i, i - 1, ..., 1$ k = i, i - 1, ..., 1 using the recurrence formulas given above. All computations are performed modulo $m$ .

  for (i = 1; i < n; i++)
  {
    scanf("%lld",&x);
    d[i] = (d[i-1] * x) % m; 

    for (j = i - 1; j > 0; j--)
      d[j] = (d[j-1] * x + d[j]) % m;

    d[0] = (d[0] + x) % m;
  }

C++

Find the maximum value among the elements of the array $d$ and store it in the variable $r es$ .

  res = 0;
  for (i = 0; i < n; i++)	   
    if (d[i] > res) res = d[i];

Print the answer.

  printf("%lld\n",res);
}