Sums of Products
National Olympiad — National round
Submission name: sumprod.cpp
Problem summary
For every k=1…n, sum the products of all choices of k distinct positions in the input sequence. Reduce each sum modulo m and output the largest remainder. Equal values at different positions remain separate choices.
Input
n m, followed by n integers a1…an.
Output
Largest remainder among the n sums.
Constraints
0<n<12345; 1<m<12345678; 0<ai<12345.
Worked example
An independently prepared example for this explanation.
Input
3 7 1 2 4
Output
1
Solution analysis
- dp[k] stores the sum of products choosing k positions processed so far; dp[0]=1.
- For each value a, update dp[k]+=a·dp[k−1] modulo m, in decreasing k order.
- Take the maximum over k≥1 after all values are processed.
Why it works
Every k-position choice either excludes the new position or includes it together with a (k−1)-position old choice. These cases are disjoint and exhaustive.
Watch out. Descending updates prevent reusing one position. The empty product dp[0] is not a candidate answer.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every k-position choice either excludes the new position or includes it together with a
// (k−1)-position old choice. These cases are disjoint and exhaustive.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<long long>d(n+1);
d[0]=1;
for(int i=1;i<=n;i++){
long long a;
cin>>a;
for(int k=i;k>=1;k--){
d[k]=(d[k]+a*d[k-1])%m;
}
}
cout<<*max_element(d.begin()+1,d.end())<<'\n';
}