Time limit per test: 2.0 seconds
Memory limit: 512 megabytes
唐纳德先生的某女性朋友最近与唐纳德先生同居。该女性朋友携带一 baby。该 baby 酷爱吃棒棒糖，且有一个奇怪的特性：今天吃的棒棒糖一定要比昨天的棒棒糖更多，至少要一样多。如果棒棒糖少了，baby 就会很不高兴；另外如果有连续 k 天棒棒糖的数量都是一样的，baby 也会很不高兴。
唐纳德先生发现他的口袋里只有可怜的 n 元钱，他可以用 1 元钱买 1 根棒棒糖。他想用这些钱逗 baby 开心，这些钱可以不花完。他可以从某一天开始再也不买棒棒糖，把他的女性朋友和 baby 一起送回家；但是他绝对不能让 baby 不高兴，否则他的女性朋友可能对他做一些不和谐的事情。
唐纳德先生想要知道，他总共有多少种买棒棒糖的方案，两种方案不相同当且仅当总天数不相同，或者某一天买的棒棒糖数量不相同。唐纳德先生知道这个问题对于聪明的你实在是太简单了，所以他加了一个附加条件：他第一天必须买棒棒糖，而且至少买 x 根棒棒糖。
Input
一行三个整数 n,x,k。
数据范围约定：
- 对于 Easy 档：1≤n,x≤100,2≤k≤100。
- 对于 Hard 档：1≤n,x≤104,2≤k≤104。
Output
输出答案模 998 244 353。
Examples
input
3 1 2
output
4
input
1 1 2
output
1
input
4 2 3
output
4
Note
样例 1：
有四种方案：
- 第一天 1；
- 第一天 2；
- 第一天 3；
- 第一天 1，第二天 2；
注意第一天和第二天都买 1 是不行的，因为连续两天棒棒糖数量一样，baby 就会很不高兴。
题意：
把n表示成a1*p1+a2*p2+a3*p3…的形式，且满足x<=a1<a2<a3..；0<p<K;
自己思路：
数的划分问题。
小数据，可以用DP或者母函数来解决，可以参考官方题解，这里不再累赘。
官方题解：
（ORZ，母函数优化背包）
Easy版本，普通母函数
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int Mod=;
int c1[],c2[],ans,x,K,p;
int n,i,j,m,k;
void _get()
{
memset(c1,,sizeof(c1));
memset(c2,,sizeof(c2));
scanf("%d%d",&x,&K);
for(k=;k<K&&k*x<=n;k++) {
c1[k*x]=;
ans=(ans+c1[k*x])%Mod;
}
for(i=x+;i<=n;i++){
for(j=;j<=n;j++)
for(k=;k*i+j<=n&&k<K;k++) {
c2[k*i+j]+=c1[j];
if(k) ans=(ans+c1[j])%Mod;
}
for(k=;k<=n;k++) {
c1[k]=c2[k];
c2[k]=;
}
}
ans=(ans+Mod-)%Mod;
}
int main()
{ while(cin>>n) {
ans=;
_get();
cout<<ans<<endl;
}
return ;
}
Hard版本，母函数优化背包。
左边的用a表示，右边的用b表示。 左边和右边分别是背包问题。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
const int Mod=;
const int maxn=;
long long a[maxn],b[maxn],c[maxn],ans;
int main()
{
int n,x,k,i,j;
scanf("%d%d%d",&n,&x,&k);
a[]=b[]=; for(i=x;i<=n;i++)
for(j=n;j>=;j--)
if(j>=i*k) a[j]=(a[j]-a[j-i*k])%Mod; for(i=x;i<=n;i++)
for(j=i;j<=n;j++)
b[j]=(b[j]+b[j-i])%Mod; for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(i+j<=n) c[i+j]=(c[i+j]+a[i]*b[j])%Mod; for(i=;i<=n;i++)
ans=((ans+c[i])%Mod+Mod)%Mod; printf("%lld\n",ans);
return ;
}
