内部题，题干不粘了。

$30分算法$

---

首先看数据范围，可以写出来一个普通dp

#include
#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
#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;
}
}

听说暴力可以AC所以我打的A*？？？

看不懂题解，如果给一个菊花图题解不就爆炸了吗？$2^{10000}$我觉得会炸

所以这个题瞎搞就行了？？？

然后我就瞎搞了个A*

跑的还特别快。大约600毫。

思路大约就是把每个直接与1相连的点拿出来，然后对于每个点跑A*，因为已经提前处理出来各种dis所以比较快。

然后没了

#include
using namespace std;
#define ll int
#define A 100010
#define in inline
ll n,m;
bool flag[A],ok=0;
ll head[A],nxt[A],ver[A],tot1=0,t;
ll head2[A],nxt2[A],ver2[A],cnt=0,tot2=0;
ll value[A],value2[A],e,d[A],len=0;
struct qnode{
ll v,w,sz,id;
friend bool operator < (qnode x,qnode y) { return x.w+d[x.v]>y.w+d[y.v];
}
};
void re()
{
tot1=1,tot2=1;
memset(flag,0,sizeof(flag));
memset(head,0,sizeof(head));memset(head2,0,sizeof(head2));
memset(ver,0,sizeof(ver));memset(ver2,0,sizeof(ver2));
memset(nxt,0,sizeof(nxt));memset(nxt2,0,sizeof(nxt2));
memset(value,0,sizeof(value));memset(value2,0,sizeof(value2));
}
in void add1(ll u,ll v,ll w)
{
ver[++tot1]=v;
nxt[tot1]=head[u];
value[tot1]=w;
head[u]=tot1;
}
in void add2(ll x,ll y,ll w)
{
ver2[++tot2]=y;
nxt2[tot2]=head2[x];
value2[tot2]=w;
head2[x]=tot2;
}
in void spfa(ll root)
{
memset(flag,0,sizeof(flag));
memset(d,0x3f,sizeof(d));
queue q;
q.push(root);
flag[root]=1;
d[root]=0;
while(!q.empty())
{
ll x=q.front();
q.pop();
flag[x]=0;
for(ll i=head[x];i;i=nxt[i])
{
ll y=ver[i],w=value[i];
if(d[y]>d[x]+w)
{
d[y]=d[x]+w;
if(!flag[y])
{
flag[y]=1;
q.push(y);
}
}
}
}
return ;
}
in ll read()
{
ll x=0,f=1;char c=getchar();
while(!isdigit(c))
{
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*f; } in ll astar() { // 从每个直接相连的点开始跑A* ll ans=0x7ffffff; for(ll i=head[1];i;i=nxt[i]) { ll y=ver[i]; priority_queue h;
memset(flag,0,sizeof(flag));
qnode s;
s.v=y,s.w=value[i],s.id=0;
h.push(s);
bool ok=0;
while(!h.empty())
{
qnode no=h.top();
// printf("当前 %d sumvalue=%d\n",no.v,no.w);
if(no.v==1){
ans=min(no.w,ans);
break;
}
h.pop();
flag[no.v]=1;
for(ll i=head2[no.v];i;i=nxt2[i]){
ll tu=ver2[i];
// printf("tu=%d\n",tu);
if(tu==1&&!ok){
ok=1;
// printf("tu=%d \n",tu);
continue;
}
if(flag[tu])
{/*printf("掠过\n");*/continue;}
// printf("没有掠过\n");
qnode t;
t.v=tu;t.w=value[i]+no.w;t.sz=no.sz+1;
h.push(t);
// printf("推入 %d->%d z=%d\n",no.v,tu,value2[i]+no.w);
}
}
}
return ans;
}

int main()
{
scanf("%d",&t);
while(t--)
{
re();
ll xx,yy;ll zz;
n=read(),m=read();
for(ll i=1;i<=m;i++) { xx=read(),yy=read();zz=read(); add1(yy,xx,zz); add1(xx,yy,zz); add2(xx,yy,zz); add2(yy,xx,zz); } spfa(1); /* for(ll i=2;i<=tot1;i++){ printf("%d\n",ver[i]); } for(ll i=1;i<=n;i++){ printf("%d\n",d[i]); } */ ok=1; ll ans=astar(); if(ans>=1000000) cout<<-1<<endl;
else
printf("%d\n",ans);
}
}