看了题目名字深切怀疑出题人是不是失恋了，然后出题折磨我们。然后这题就愉快的打了个暴力，最后莫名其妙wa20，伤心.....
其实这题正解不是很难想，如果说把暴力的DP搞出来，正解也差不到哪去了，
我们发现此题中暴力的话
一层枚举D即天数，另一层枚举当前给过的饼干数j，然后还有一层枚举上一层的饼干数，（当然还可以通过前缀和删去一维）
但是我们观察数据范围，发现D及其的大！！！！！！！
显然枚举中不能出现D
有一条显然的性质，如果你有N块饼干，那么最多给N天，每天给一块就会给完。
那么我们第一维枚举至N，表示每一天一定给
最后统计答案时（i：1～N）f[i][N]*C(D,i);即可
（本题中D过大，所以不能用逆元，改用递推O(n)求，*(D-i)时要取模，不然会暴）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 #define ll long long 8 using namespace std; 9 #define MAXN 2010 10 const ll mod=998244353; 11 ll f[MAXN][MAXN]; 12 ll N,D,M; 13 ll ni[MAXN],ni_c[MAXN]; 14 ll a[MAXN][MAXN]; 15 ll max1(ll x,ll y) 16 { 17 return (x>y)?x:y; 18 } 19 ll min1(ll x,ll y) 20 { 21 return (x<y)?x:y; 22 } 23 void work() 24 { 25 f[0][0]=1;a[0][0]=1; 26 for(ll i=1;i<=N;++i) 27 { 28 ll R=min(N,(M-1)*i); 29 for(ll j=1;j<=N;++j) 30 { 31 a[i-1][j]=(a[i-1][j-1]+f[i-1][j]+mod)%mod; 32 } 33 for(ll j=i;j<=R;++j) 34 { 35 ll L=max1(i-1,j-M+1); 36 /*for(ll k=L;k<=j-1;++k) 37 { 38 f[i][j]=(f[i][j]+f[i-1][k])%mod; 39 }*/ 40 f[i][j]=(f[i][j]%mod+(a[i-1][j-1]-a[i-1][L-1]+mod)%mod+mod)%mod; 41 //printf("f[%lld][%lld]=%lld ",i,j,f[i][j]); 42 } 43 } 44 ll sum=0ll;ll ans=1ll; 45 for(ll i=1;i<=N;++i) 46 { 47 if(i>D)continue; 48 ans=(ans*((D-i+1)%mod)+mod)%mod; 49 sum=(sum+(f[i][N]*(ans*ni_c[i]%mod+mod)+mod)%mod+mod)%mod; 50 //printf("f=%lld C=%lld ",f[i][N],C(D,i)); 51 } 52 printf("%lld ",sum%mod); 53 } 54 int main() 55 { 56 // freopen("text.in","r",stdin); 57 // freopen("wa.out","w",stdout); 58 ni_c[1]=1;ni[1]=1; 59 ni_c[0]=1;ni[0]=1; 60 for(ll i=2;i<=2000;++i) 61 { 62 ni[i]=((mod-mod/i)*ni[mod%i])%mod; 63 ni_c[i]=(ni_c[i-1]*ni[i])%mod; 64 } 65 while(cin>>N>>D>>M) 66 { 67 if(N==0&&D==0&&M==0)break; 68 memset(f,0,sizeof(f)); 69 memset(a,0,sizeof(a)); 70 work(); 71 } 72 }