Bounded-Sum Sequences
National Olympiad — Regional round
Submission name: sequences.cpp
Problem summary
Count ordered sequences of n nonnegative integers, each less than p, whose sum is strictly less than s.
Input
p n s.
Output
The exact number of sequences.
Constraints
0 < p < s < 30; 0 < n < 20.
Worked example
An independently prepared example for this explanation.
Input
3 2 3
Output
6
Solution analysis
- dp[t] counts prefixes with sum t. Initially dp[0]=1.
- For every new position append each value 0…p−1 while retaining sums below s. Add all final states.
Why it works
Every sequence has one unique last value and prefix. The recurrence counts each valid extension once; nonnegative values mean discarded sums can never become valid later.
Complexity: O(nsp) time, O(s) space.
Watch out. The bound is strict. A 64-bit count suffices: even unrestricted compositions with sum≤28 and length≤19 number at most C(47,19), below 2⁶³.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every sequence has one unique last value and prefix. The recurrence counts each valid
// extension once; nonnegative values mean discarded sums can never become valid later.
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<iterator>
using namespace std;
int main(){
int p,n,s;
cin>>p>>n>>s;
vector<long long>dp(s);
dp[0]=1;
for(int i=0;i<n;i++){
vector<long long>next(s);
for(int t=0;t<s;t++){
for(int x=0;x<p&&t+x<s;x++){
next[t+x]+=dp[t];
}
}
dp.swap(next);
}
cout<<accumulate(dp.begin(),dp.end(),0LL)<<'\n';
}