3448. 比昨天更多的棒棒糖 (Easy)
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
≤
10
4
,
2
≤
k
≤
10
4
。
Output
输出答案模
998
244
353
。
Examples
3 1 2
4
1 1 2
1
4 2 3
4
Note
样例 1：
有四种方案：
- 第一天 1；
- 第一天 2；
- 第一天 3；
- 第一天 1，第二天 2；
注意第一天和第二天都买 1 是不行的，因为连续两天棒棒糖数量一样，baby 就会很不高兴。
#include <bits/stdc++.h>
using namespace std;
#define modo 998244353
long long dp[101][101][101];
int main(){
int n, x, k;
cin>>n>>x>>k;
long long ans = 0;
memset(dp, 0, sizeof(dp));
for(int i = x; i <= n; ++i){
dp[i][i][1] = 1;
ans++;
for(int j = x; j < i; ++j){
for(int l = x; l < j; ++l){
for(int z = 1; z <= k; ++z){
dp[i][j][1] += dp[i - j][l][z];
dp[i][j][1] %= modo;
}
}
ans += dp[i][j][1];
ans %= modo;
for(int z = 2; z < k; ++z){
dp[i][j][z] += dp[i - j][j][z - 1];
dp[i][j][z] %= modo;
ans += dp[i][j][z];
ans %= modo;
}
}
}
cout<<ans<<endl;
}
/*
题意：
一共n元，每天需要买糖果给宝宝吃，且至少大于等于前一天的量，第一天最少为x，问有多少种购买方案。
思路：
说实话。。。写一个n^4方dp感觉很丢人。。dp[i][j][k]表示花了i元，当天花j元，这是k天花了j元时有多少种方案。
转移似乎很简单。。。结束。。
*/