比较好想的一道题,只是那个组合数比较恶心。
先说一下我最开始想的$n^4$的沙雕dp:
设f[i][j][k]为前i天给了j个,第i天给了k个,则f[i][j][k]=∑f[i-1][j-k][o];
复杂度凑起来大概是$n^4$,因为本来就是针对30%打的,没有考虑特别大的d。
观察上面的式子,发现第三维并没有什么卵用,把它干掉,f[i][j]表示前i天给j个,那么f[i][j]=∑f[i-1][k](j-m+1<=k<=j),复杂度$n^2d$,显然可以用前缀和优化,复杂度$nd$。
但是d太大还是会死,有位巨佬用矩阵快速幂优化拿到了90分%%%,貌似矩阵有什么规律(然而我并不会)。
题目中d很大,但是n却很小,所以实际有用的只有n天,所以递推到第n天后乘以$C_d^n$,这样对吗?根据以上状态定义,n天也不一定全部都给饼干,所以乘以$C_d^n$会算重,这个时候状态就要稍微修改一下,f[i][j]表示前i天共给了j个,且每天给的饼干数>0,这样就解决了重复的问题,那么最后答案就是$∑f[i][n]*C_d^i$.
然而他又爆了longlong,__int128拯救世界系列。
#include<iostream>
#include<cstring>
#include<cstdio>
#define int LL
#define LL __int128
#define mod 998244353
#define ma(x) memset(x,0,sizeof(x))
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int n,m;
LL d;
inline LL read()
{
LL s=;char a=getchar();
while(a<''||a>'')a=getchar();
while(a>=''&&a<=''){s=s*+a-'';a=getchar();}
return s;
}
LL f2[][];
LL poww(LL a,int b)
{
LL ans=;
while(b)
{
if(b&)ans=(ans*a)%mod;
a=(a*a)%mod;
b=b>>;
}
return ans;
}
LL C(LL d,LL n)
{
LL jn=,js=;
for(int i=;i<=n;i++)jn=(jn*i)%mod;
for(int i=d-n+;i<=d;i++)js=(js*i)%mod;
return js*poww(jn,mod-)%mod;
}
signed main()
{
// freopen("in.txt","r",stdin);
// freopen("0.out","w",stdout); while(scanf("%lld%lld%lld",&n,&d,&m))
{
if(!n&&!d&&!m)return ;
ma(f2);
if(1ll*d*(m-)<n){puts("");continue;}
if(d<=n)
{
for(int i=;i<m;i++)f2[][i]=;
for(int i=;i<=d;i++)
{
LL sum=;
for(int j=;j<=n;j++)
{
sum=(sum+f2[i-][j]);
if(j-m>=)sum=((sum-f2[i-][j-m])%mod+mod)%mod;
f2[i][j]=(f2[i][j]+sum)%mod;
}
}
LL ans=f2[d][n];
printf("%lld\n",ans%mod);
}
else
{
for(int i=;i<m;i++)f2[][i]=;
for(int i=;i<=n;i++)
{
LL sum=;
for(int j=max(,i-m);j<i;j++)sum=(sum+f2[i-][j])%mod;
for(int j=i;j<=n&&j<=i*(m-);j++)
{
if(j-m>=)sum=((sum-f2[i-][j-m])%mod+mod)%mod;
f2[i][j]=(f2[i][j]+sum)%mod;
sum=(sum+f2[i-][j]);
}
}
LL ans=;
for(int i=;i<=n;i++)
ans=(ans+f2[i][n]*C(d,i))%mod;
printf("%lld\n",ans%mod);
}
}
}