题目链接：https://www.luogu.org/problemnew/show/P4457
发现不能直接记忆化搜索，因为当前可能状态可能转移到血量+1的状态，但可以发现如果血量为上限值时就没有这种情况了，因此先写出每一个状态的转移式，为一串其他状态*系数+常数，然后从第n位下来把每一个状态转移式中>=当前状态血量的状态消去，再dfs即可。
代码：
#include<bits/stdc++.h> #define ll long long using namespace std; const ll mod=1e9+7; const int N=1510; ll n,p,m,k,f[N],xs[N][N],cs[N],C[N],jc[N],ijc[N],X,Y,g[N]; void Ad(ll &x,ll y) {x+=y;if(x>=mod)x-=mod;} void Dw(ll &x,ll y) {x=(x>=y)?x-y:x-y+mod;} ll qpow(ll x,ll y) { ll res=1; while(y) { if(y&1)res=res*x%mod; x=x*x%mod,y>>=1; } return res; } void f__k(int x) { ll tp; if(xs[x][x+1]) { tp=xs[x][x+1]; xs[x][x+1]=0; for(int i=x;i>=0;i--) Ad(xs[x][i],tp*xs[x+1][i]%mod); Ad(cs[x],tp*cs[x+1]%mod); } if(xs[x][x]) { tp=1; Dw(tp,xs[x][x]); tp=qpow(tp,mod-2); xs[x][x]=0; for(int i=0;i<x;i++) xs[x][i]=xs[x][i]*tp%mod; cs[x]=cs[x]*tp%mod; } } void get_xs(ll x) { for(int i=0;i<=min(k,x);i++) xs[x][x+1-i]=X*Y%mod*C[i]%mod*g[i]%mod; for(int i=0;i<=min(k,x);i++) Ad(xs[x][x-i],m*Y%mod*X%mod*C[i]%mod*g[i]%mod); cs[x]=1; } ll dfs(int nw) { if(f[nw]!=-1)return f[nw]; f[nw]=cs[nw]; for(int i=nw-1;i>=0;i--) Ad(f[nw],xs[nw][i]*dfs(i)%mod); return f[nw]; } bool check() { if(k==0)return 1; if(m==0) { if(k==1) { if(n>1)return 1; } } return 0; } int main() { int T;ll tp; jc[0]=1; for(int i=1;i<N;i++) jc[i]=jc[i-1]*i%mod; ijc[N-1]=qpow(jc[N-1],mod-2); for(int i=N-2;i>=0;i--) ijc[i]=ijc[i+1]*(i+1)%mod; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld%lld",&n,&p,&m,&k); if(check()){puts("-1");continue;} memset(xs,0,sizeof xs),memset(cs,0,sizeof cs); for(int i=0;i<=p;i++)f[i]=-1;f[0]=0,tp=1; for(int i=0;i<=n&&i<=k;i++) { C[i]=tp*ijc[i]%mod; tp=tp*(k-i)%mod; } X=qpow(m+1,k),X=qpow(X,mod-2),Y=qpow(m+1,mod-2); for(int i=0;i<=n&&i<=k;i++) g[i]=qpow(m,k-i); for(int j=0;j<=min(k,n);j++) xs[n][n-j]=X*C[j]%mod*g[j]%mod; cs[n]=1,f__k(n); for(int i=n-1;i>=1;i--) get_xs(i),f__k(i); printf("%lld\n",dfs(p)); } }
