1525. A Grouping Problem

You are given a set of n integers. You can take k different elements from them to make a group. Two groups will be different if there is at least one element which is not common to both. For example, if there are 4 elements a, b, c, d and you are asked to take two elements then ab, ad, bc, cd are all valid and different groups. A grouping system is complete if for a particular k, number of different groups is the maximum. In the former case, {ab, bc, cd, bd, ad, ac} is a complete grouping system.

For a particular complete grouping system, the fitness is calculated in the following way:

1. Each group of a grouping system contributes a part – the multiplication of all numbers of that group;

2. Contribution from all groups are added;

3. The fitness is equivalent to Total Contribution mod m, m is the bounding parameter.

In our example, for k = 2, the fitness is F₂ = (ab + bc + cd + bd + ad + ac) mod m. If k = 1, then fitness is F₁ = (a + b + c + d) mod m.

You have to find the complete grouping system with maximum fitness.

Input. Each test case starts with two positive integer n (2 ≤ n ≤ 1000) and m (1 ≤ m < 2³¹). In next few lines there will be n positive integers. Each integer will be at best 1000. Input will be terminated by a case where n = m = 0.

Output. For each test case, print in a line the maximum fitness possible for a grouping system.

Sample input	Sample output
4 10 1 2 3 4 4 100 1 2 3 4 4 6 1 2 3 4 0 0	5 50 5

SOLUTION

dynamic programming

Algorithm analysis

Let а₁, a₂, …, a_n be the given n numbers. Let F_ik (i ≥ k) be the sum of all possible products of k numbers, taken among the first i numbers a₁, …, a_i. Construct the following table F_ik:

For four numbers, respectively, we get:

· F_4,1 = a₁ + a₂ + a₃ + a₄;

· F_4,2 = a₁a₂ + a₁a₃ + a₁a₄ + a₂a₃ + a₂a₄ + a₃a₄;

· F_4,3 = a₁a₂a₃ + a₁a₂a₄ + a₁a₃a₄ + a₂a₃a₄;

· F_4,4 = a₁a₂a₃a₄;

We have the following recurrence relations:

F_i1 = F_(i-1)1 + a_i, F_ii = F_{(i-1) (i-1)} * a_i, 1 ≤ i ≤ n

F_ik = F_(i-1)k + F_{(i-1) (k-1)} * a_i, 1 £ i £ n, 1 < k < i

For example,

· F_3,2 = F_2,2 + F_2,1 * a₃ = a₁a₂ + (a₁ + a₂) * a₃ = a₁a₂ + a₁a₃ + a₂a₃;

· F_4,3 = F_3,3 + F_3,2 * a₄ = a₁a₂a₃ + (a₁a₂ + a₁a₃ + a₂a₃) * a₄ =

a₁a₂a₃ + a₁a₂a₄ + a₁a₃a₄ + a₂a₃a₄

The values of each of the following line are recalculated through the values of the previous line, so it is enough to store in a memory only one linear array d of size 1000. The recalculation of the values in the i – th line must be started from the end: first compute the value of F_ii, then compute F_i(i-1) and so on till F_i1. The calculations should be performed modulo m.

Example

Consider the first test case. Let’s construct two tables: in the second one the calculations will be performed modulo m = 10, and in the first one no.

For example,

· F_4,2 = F_3,2 + F_3,1 * 4 = 11 + 6 * 4 = 35;

· F_4,3 = F_3,3 + F_3,2 * 4 = 6 + 11 * 4 = 50;

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

Algorithm realization

Declare the linear array d, where we shall recalculate the values F_ik.

long long d[1000];

Print the number of elements n and the value of m. For each input test set all elements of d to zero. Assign the first element a₁ to d[0].

while(scanf("%lld %lld",&n,&m), n + m > 0)

{

memset(d,0,sizeof(d));

scanf("%lld",&d[0]);

Read the value of x = a_i+1 (1 £ i < n) and recalculate the values F_ik, k = i, i – 1, …, 1 using the recurrent formulas given above. Do all computations by 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;

}

Find the maximum value among the elements of array d and assign it to the variable res.

res = 0;

for(i = 0; i < n; i++)

if (d[i] > res) res = d[i];

Print the answer.

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

}