题目链接

https://vjudge.net/contest/398864#problem/B

解题思路

规定仅顺序不同的方案为同一个方案。
因此，我们就要限制一下寻找的方法：
找到的这一串数，必须是单调的，如果不是单调寻找必然会存在重复方案。
样例为例，以1开头的：1 1 5，1 2 4，1 3 3，2 2 3不规定单调增的话：1 1 5，1 2 4，1 3 3，1 4 2……不再列举下去了，显然已经出现重复的了。
这也就是说，每个数的列举都是有范围的。
样例，第一位只能列举1，2；当第一位为1时，第二位列举1，2，3，当第一位为2时，第二位列举2；……。
这有什么规律吗？
理解一下，并不是靠找规律，可以发现当前位必须不小于前一位（毋庸置疑，因为递增），且当前位不能超过剩下数的平均值（样例，已经列举了第一位为2，那么剩下的数为7-2=5，此时要求第二位数必须不小于2，且不超过5，所以第二位可以尝试的范围为[2,5]；同样的，再确定第二位为2时，第三位的可尝试列举范围为[2,3]）
这样一来，我们就可以用dfs解决了。
（真没想到是dfs，以为是数学题，能直接算出答案）

AC代码

#include<bits/stdc++.h>
#define sc(x,y) scanf("%d%d",&x,&y)
#define pr(x) printf("%d",x)
using namespace std;
int n,k,cnt;
void dfs(int pre,int sum,int step){//pre代表前一位列举的数，sum代表当前位之前的和，step代表进行到第几位的列举了
    if(step==k) {cnt++;return ;}
    for(int i=pre;i<=(n-sum)/(k-step+1);i++)
        dfs(i,sum+i,step+1);
}
int main(){
    sc(n,k);
    dfs(1,0,1);//第一位要从1开始尝试列举，且第一位之前的和为0
    pr(cnt);
}