Expert.
Put your skills to the test.

Problem summary

Partition N employees into K nonempty groups. Only the multiset of group sizes matters; employees and exhibition labels do not distinguish configurations. Count the configurations exactly.

Constraints

1 ≤ K ≤ N ≤ 800; memory limit 16 MB.

Worked example

Official statement example.

6 2

3

Solution analysis

1. Sort the K positive sizes and subtract one from each. This gives a partition of S=N−K into at most K positive parts, with zero entries discarded.
2. Conjugating a partition exchanges its number of parts and its largest part. Thus count partitions of S using sizes 1 through K. Initialize dp[0]=1 and process each allowed size c, adding dp[s−c] to dp[s] in increasing s order.
3. For N=6,K=2, the residual total is 4. Using sizes 1 and 2 gives 1+1+1+1, 2+1+1, and 2+2, corresponding to original groups {1,5},{2,4},{3,3}. Counts exceed 64 bits, so a small decimal big integer is used.

Why it works

Subtraction and partition conjugation are bijections. After processing c, dp[s] counts every partition of s with largest part at most c once: partitions either omit c or remove one c and leave a partition counted by dp[s−c]. Therefore dp[N−K] is exactly the requested count.

Watch out. Do not count ordered compositions.,Increasing sum order permits repeated parts.,The answer requires arbitrary precision.

An independently written complete program with standard headers.

// Key idea: Subtraction and partition conjugation are bijections. After processing c, dp[s] counts
// every partition of s with largest part at most c once: partitions either omit c or remove one c and
// leave a partition counted by dp[s−c].
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<vector>
using namespace std;
struct Big{
    vector<int>d;
    Big(int x=0):d(1,x){
    }
    void add(const Big&b){
        size_t n=max(d.size(),b.d.size());
        d.resize(n,0);
        long long carry=0;
        for(size_t i=0;i<n;++i){
            long long z=d[i]+carry;
            if(i<b.d.size()){
                z+=b.d[i];
            }
            d[i]=int(z%1000000000);
            carry=z/1000000000;
        }
        if(carry){
            d.push_back(int(carry));
        }
    }
};
int main(){
    int n,k;
    cin>>n>>k;
    int s=n-k;
    vector<Big>dp(s+1);
    dp[0]=Big(1);
    for(int c=1;c<=k&&c<=s;++c){
        for(int j=c;j<=s;++j){
            dp[j].add(dp[j-c]);
        }
    }
    const auto&d=dp[s].d;
    cout<<d.back();
    for(int i=int(d.size())-2;i>=0;--i){
        cout<<setw(9)<<setfill('0')<<d[i];
    }
    cout<<'\n';
}