Nonincreasing Partitions
National Olympiad — Regional round (2018 season)
Submission name: seq.cpp
Problem summary
Count positive nonincreasing integer sequences with sum n and all elements at most m.
Input
Two integers n and m.
Output
The exact number of sequences.
Constraints
2 ≤ n,m ≤ 269.
Worked example
An independently prepared example for this explanation.
Input
6 5
Output
10
Solution analysis
- A nonincreasing sequence is uniquely specified by how many times it uses each value 1…m. This is an unordered coin-change count rather than a count of compositions.
- Set ways[0]=1. Process each allowed part value v in increasing order and update sums s=v…n by ways[s]+=ways[s-v]. Increasing sums permit repeated uses of v; the outer value loop prevents different orders from being counted.
- For n=6 and m=5, all partitions of 6 are allowed except the single part 6. The ten possibilities include 5+1, 4+2, 3+3 and six copies of 1. Exact values fit unsigned 64-bit integers: every answer is at most the unrestricted partition count p(269).
Why it works
After processing v, ways[s] counts multisets of values from 1…v with sum s. Such a multiset either contains no v (the old ways[s]) or can remove one v to obtain a multiset counted by the already updated ways[s-v]. These cases are disjoint and exhaustive. Sorting each multiset decreasingly gives exactly the required sequences.
Watch out. Do not reverse the loop order, which would count ordered compositions. Use 64-bit values and initialize the empty-sum count to 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<unsigned long long>ways(n+1);
ways[0]=1;
for(int part=1;part<=min(n,m);part++){
for(int sum=part;sum<=n;sum++){
// Ascending sums allow any number of this part.
ways[sum]+=ways[sum-part];
}
}
cout<<ways[n]<<'\n';
}