a bit of uva: UVa 11026 - A Grouping Problem

Problem Statement:
UVa 11026 - A Grouping Problem

Summary:
We are given $a_1,a_2,\ldots,a_n$ and a number $K$ which defines the sum of products of permutation of length K, e.g. $K=1$ is $a_1+a_2+\ldots+a_n$, $K=2$ is $a_1a_2 + a_2a_3+ \ldots + a_{n-1}a_n$ and so on and so forth. Find the maximum of these sum of products $\mod{M}$.

Solution:
Despite the technicality, this problem has a very nice recursive formulation:
Let $S(k,n)$ be the sum of products of permutation of length $k$ amongst $n$ elements. Then we have $S(k,n) = a_n * S(k-1,n-1) + S(k, n-1)$. This is actually derived from the factorization of $a_n$ from all the terms that contain $a_n$. From here, we can do a bottom-up DP to arrive at the answer. Here is a sample implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long Long;
Long MOD, a[1003], dp[1003][1003];
int N;
// Recursion: S(k, n) = a_n * S(k-1, n-1) + S(k, n-1)

int main(){
    for(int i=0;i<1003;++i){
        dp[0][i] = 1;
    }
    while(cin >> N >> MOD){
        if(N+MOD == 0) break;
        for(int i=1;i<=N;++i){
            cin >> a[i];
        }
        for(int i=1;i<=N;++i){
            for(int j=i;j<=N;++j){
                dp[i][j] = (a[j] * dp[i-1][j-1])%MOD;
                if(j > i) dp[i][j] += dp[i][j-1];
                dp[i][j] %= MOD;
                if(dp[i][j] < 0) dp[i][j] += MOD;
            }
        }
        Long ans = 0;
        for(int i=1;i<=N;++i){
            ans = max(ans, dp[i][N]);
        }
        cout << ans << endl;
    }
    return 0;
}