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;
}