Problem F
A Grouping Problem
Input: Standard Input

Output: Standard Output

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.

Here, in this problem 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                             Output for Sample Input

4 10

1 2 3 4

4 100

1 2 3 4

4 6

1 2 3 4

0 0

Problem setter: Md. Kamruzzaman, EPS

題目描述：

在 n 個數字中，任挑 k 個數字相乘並且加總，最後對 M 取模。

問在所有 k (1 <= k <= n) 之中，數字最大為何？

題目解法：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*A[i] (分成有無 A[i] 的兩部分)

// dp[i-1][j] 沒有 A[i] 的在前 i-1 個數字挑 j 個相乘的總合

// dp[i-1][j-1]*A[i] 有 A[i] 的在前 i-1 個數字挑 j-1 個相乘的總合

i 表示放入前 i 個數字, j 表示幾個數字連乘積的和。

按照 dp 方程計算之即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long dp[1005][1005];
int main() {
    int n, m, A[1005], i, j;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n+m == 0)    break;
        for(i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        dp[0][0] = 1;
        for(i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for(j = 1; j <= i; j++) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*A[i];
                if(dp[i][j] >= m)
                    dp[i][j] %= m;
            }
        }
        long long ret = 0;
        for(i = 1; i <= n; i++)
            ret = max(dp[n][i], ret);
        printf("%lld\n", ret);
    }
    return 0;
}