写给DP新手的题解（好吧我也是蒟蒻（

首先，我们推一下式子

我们令$f[j]$来表示我们选择到第j元钱的方案数

那么我们枚举一个$i$表示我们当前选了$j-i$元钱的东西，然后又选了这么一个价值为i的物品

那么我们肯定要保证$i<j$吧？

$\sum\limits_{i=1}^{k}\sum\limits_{j=i}^{n}f[j]+=f[j-i];$

为什么这里的是$f[j]+=f[j-i]$呢？

我们可以发现，当$f[j-i]$转移到$f[j]$的时候，$f[j-i]$已经有了一些情况（显而易见（因为在枚举$f[j]$之前，必定先枚举的$f[j-i]$，那么在转移的时候就不会出现像$f[j]$转移了，$f[j-i]$没转移的情况

但是我们又发现，这肯定是炸$longlong$的

所以我们用了个小技巧——int128

这是一个能存128位的东西（应该是吧？

（但是在本地编译器会炸（别问我为什么（我也不知道

copy代码时间！

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
__int128 f[10001];
void write(__int128 x)
{
    if(x>9) write(x/10);//如果x>9的话就递归它的最高位，再往下依次输出 
    putchar(x%10+'0');//输出这个数的末尾/kk（+'0'是为了让它转成字符类型的 
}
int main()
{
	int n,k;
	cin>>n>>k;
	f[0]=1;//初始化！让n为0时的方案数为1 
	for(int i=1;i<=k;i++)//枚举每一个物品 
	{
		for(int j=i;j<=n;j++)//必须大于i，否则买不了/kk 
		{
			f[j]+=f[j-i];//那么这个方案数就是上面所推导的一坨 
		}
	}
	write(f[n]);//要用__int128否则会炸longlong（ull也好像不行 
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
__int128 f[N]; 
template<typename T> void qw(T x){
	if(x<0) x=-x, putchar('-');
	if(x>=10) qw(x/10);
	putchar(x%10+'0');
}
int main(){
	int n, K; scanf("%d%d", &n, &K);
	f[0]=1;
	for(int i=1; i<=K; i++){
		for(int j=i; j<=n; j++){
			f[j]+=f[j-i];
		}
	}
	qw(f[n]); printf("\n");
	return 0;
}