Ordered Partitions
National Olympiad — National round
Submission name: partition.cpp
Problem summary
Count ordered sequences of integers at least 3 whose sum is N. The number of terms is unrestricted; different orders count separately.
Input
One integer N.
Output
The count modulo 1,000,000,007.
Constraints
3 ≤ N ≤ 100,000. Partial tests: N ≤ 20 (30%) and N ≤ 10,000 (70%).
Worked example
An independently prepared example for this explanation.
Input
7
Output
3
Solution analysis
- Let dp[s] count valid ordered sequences summing to s, with dp[0]=1 for the empty prefix.
- Choosing the final term gives dp[s]=sum(dp[t],0≤t≤s−3). Maintain this prefix sum while increasing s.
Why it works
Every nonempty sequence has one uniquely determined last term at least 3 and a valid prefix. The transition enumerates each prefix/last-term pair exactly once, retaining order.
Complexity: O(N) time and O(N) memory.
Watch out. These are compositions, not unordered integer partitions. dp[0]=1 is necessary.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
const int MOD=1000000007;
vector<int>dp(n+1);
dp[0]=1;
long long prefix=0;
for(int s=1;s<=n;s++){
if(s>=3){
prefix=(prefix+dp[s-3])%MOD;
}
dp[s]=prefix; // All legal final terms, in O(1).
}
cout<<dp[n]<<'\n';
}