内部题，题干不粘了。
$30分算法$
首先看数据范围，可以写出来一个普通dp
#include<bits/stdc++.h> #define ll int #define A 2100 #define mod 998244353 using namespace std; ll f[1501][A+A+A],n,d,m; int main() { scanf("%d%d%d",&n,&d,&m); while(n!=0&&d!=0&&m!=0){ memset(f,0,sizeof(f)); f[0][0]=1; for(ll i=1;i<=d;i++) f[0][i]=1; for(ll i=1;i<=n;i++) for(ll k=1;k<=d;k++) { for(ll j=min(m-1,i);j>=0;j--) if(i-j>=0) f[i][k]=(f[i][k]+f[i-j][k-1])%mod; } printf("%d\n",f[n][d]); scanf("%d%d%d",&n,&d,&m); } }
d最大为$1e^12$所以你这个dp会完美T掉或者M掉
$100分算法$
观察，发现n的范围非常小，m的范围也特别小。
所以我们利用这条性质，先片面的忽视掉这一天不给她饼干的情况，我们设定$f$定义为每天都给她饼干的情况。
设$f[i][j]$中i表示为前$i$天目前给了$j$个饼干的情况
然后可以推出来方程式
可以给她1～m-1个饼干
$f[i][j]=\sum_\limits {k=(j-M-1)}^{k<=j-1} f[i-1][k]$
然后直接转移，复杂度仍然难以接受，观察dp式子发现它是由一个字段转移过来的，我们要用前缀和维护优化一下。
仍然AC不了？
可能你会乘爆long long
注意多取模
#include<bits/stdc++.h> #define ll long long #define A 2010 #define mod 998244353 using namespace std; ll f[A][A],n,m,q,d; ll sum[A]; ll meng(ll x,ll k) { ll ans=1; for(;k;k>>=1,x=x*x%mod) if(k&1) ans=x*ans%mod; return ans%mod; } int main(){ while(1){ scanf("%lld%lld%lld",&n,&d,&m); ll ans=0; if(n==0&&d==0&&m==0){ return 0; } memset(f[1],0,sizeof(f[1])); f[0][0]=1; for(ll i=1;i<=min(n,m-1);i++) f[1][i]=1; for(ll i=2;i<=n;i++){ for(ll j=0;j<=n;j++) sum[j]=(sum[j-1]%mod+f[i-1][j]%mod)%mod; for(ll j=1;j<=n;j++) f[i][j]=(sum[j-1]%mod-sum[max(j-m,0ll)]%mod+mod)%mod; } ll sd=d%mod; for(ll i=1;i<=min(n,d);i++) { if(i==1) ans=(ans+sd*f[i][n]%mod)%mod,ans%=mod; else{ sd=(sd%mod*meng(i,mod-2)%mod*((d-i+1)%mod))%mod; ans%=mod; ans=(ans+f[i][n]%mod*sd%mod)%mod; } // if(sd!=0)printf("sd=%lld ans=%lld f*s=%lld\n",sd,ans,f[i][n]*sd%mod); } cout<<(ans+mod)%mod<<endl; } }
原文：https://www.cnblogs.com/znsbc-13/p/11218768.html
