高斯消元算DP
(f_i)表示k次减血减(i)滴血的概率
(f_i=frac{C_k^im^{k-i}}{(m+1)^k})可以递推求出
然后方程的系数就很好算了
血量减爆的情况只与(E_0)的系数有关，但(E_0=0)所以不用管
等等，(n=1500)怎么高斯消元？
发现矩阵呈近似下三角矩阵
110000
111000
111100
111110
111111
111111
每行我们就只消两列，把上述矩形消成
（具体来说应该是一列一列地消，只是消到那一行时，就只有两个未知量了，用来消别的行）
110000
011000
001100
000110
000011
000001
最后一行只有一个未知量，可以回代求解
（实在扯不清楚就只能看代码了）
时间复杂度(O(n^2))
还有一种方法，移项后发现f[1]只和f[2]相关，因此设f[1]=x
其他未知量都可以通过x表示出来，代到f[n]的方程里就解出x
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int 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^48);c=getchar();}
return f==1?x:-x;
}
const int N=1504,mod=1e9+7;
int n,p,m,k,inv,inv1,a[N][N],f[N];
inline int ksm(int x,int r){
int ret=1;
for(int i=0;(1ll<<i)<=r;i++){
if((r>>i)&1)ret=ret*x%mod;
x=x*x%mod;
}
return ret;
}
inline void solve(){
n=read();p=read();m=read();k=read();
if(!k){puts("-1");return;}
if(!m){
if(k==1){puts("-1");return;}
int ret=0;
for(;p>0;p-=k,ret++)
if(p<n)p++;
cout<<ret<<"
";
return;
}
inv=ksm(m,mod-2);inv1=ksm(m+1,mod-2);
f[0]=ksm(m*inv1%mod,k);
for(int i=1;i<=min(n+1,k);i++)
f[i]=f[i-1]*inv%mod*ksm(i,mod-2)%mod*(k-i+1)%mod;
for(int i=1;i<n;i++)
for(int j=1;j<=i;j++)
a[i][j]=(f[i-j]*m+f[i-j+1])%mod*inv1%mod;
for(int i=1;i<n;i++)
a[i][i+1]=f[0]*inv1%mod;
for(int i=1;i<=n;i++)
a[i][n+1]=mod-1;
for(int i=1;i<=n;i++)
a[n][i]=f[n-i];
for(int i=1;i<=n;i++)
a[i][i]=(a[i][i]+mod-1)%mod;
for(int i=1,tmp;i<=n;i++){//两列两列消
inv=ksm(a[i][i],mod-2);
a[i][i]=1;
a[i][n+1]=a[i][n+1]*inv%mod;
if(i!=n)a[i][i+1]=a[i][i+1]*inv%mod;
for(int j=i+1;j<=n;j++){
tmp=a[j][i];
a[j][i+1]=(a[j][i+1]-tmp*a[i][i+1]%mod+mod)%mod;
a[j][n+1]=(a[j][n+1]-tmp*a[i][n+1]%mod+mod)%mod;
}
}
for(int i=n;i>1;i--)
a[i-1][n+1]=(a[i-1][n+1]-a[i-1][i]*a[i][n+1]%mod+mod)%mod;
cout<<a[p][n+1]<<"
";
}
inline void clear(){
for(int i=1;i<=min(n+1,k);i++)f[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)a[i][j]=0;
}
signed main(){
int T=read();
while(T--){
solve();
clear();
}
return (0-0);
}