#include using namespace std; #define int long long const int N=1505; const int mod=1e9+7; int T,n,p,m,k; int a[N][N],c[N][N],f[N],inv,inv1; int qpow(int x,int y){ int ans=1; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } void init(){ inv=qpow(m+1,mod-2),inv1=qpow(m,mod-2),f[0]=qpow(m*inv%mod,k); for(int i=1;i1;i--){ a[i-1][n+1]=(a[i-1][n+1]-a[i-1][i]*a[i][n+1]%mod+mod)%mod; a[i-1][i]=0; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); for(int i=1;i>T; while(T--){ memset(a,0,sizeof a),memset(f,0,sizeof f); cin>>n>>p>>m>>k; if(k==0){ cout0){ if(cur `#include using namespace std; #define int long long const int N=1505; const int mod=1e9+7; int T,n,p,m,k; int a[N][N],c[N][N],f[N],inv,inv1; int qpow(int x,int y){ int ans=1; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } void init(){ inv=qpow(m+1,mod-2),inv1=qpow(m,mod-2),f[0]=qpow(m*inv%mod,k); for(int i=1;imin(n+1,k);i++) f[i]=f[i-1]*inv1%mod*qpow(i,mod-2)%mod*(k-i+1)%mod; } void gauss(){ for(int i=1;i int inv=qpow(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 int mult=a[j][i]; a[j][i]=0; if(i!=n) a[j][i+1]=(a[j][i+1]-mult*a[i][i+1]%mod+mod)%mod; a[j][n+1]=(a[j][n+1]-mult*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; a[i-1][i]=0; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); for(int i=1;i c[i][0]=1; for(int j=1;jc[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } cin>>T; while(T--){ memset(a,0,sizeof a),memset(f,0,sizeof f); cin>>n>>p>>m>>k; if(k==0){ cout"-1\n"; continue; } if(m==0){ if(k==1) cout"-1\n"; else{ int ans=0,cur=p; while(cur>0){ if(cur cur-=k,ans++; } cout"\n"; } continue; } init(); for(int i=1;i for(int j=1;ja[i][j]=(f[i-j]*m%mod+f[i-j+1])%mod*inv%mod; a[i][i+1]=f[0]*inv%mod,a[i][i]=(a[i][i]-1+mod)%mod,a[i][n+1]=mod-1; } for(int i=1;ia[n][i]=f[n-i]; a[n][n]=(a[n][n]-1+mod)%mod,a[n][n+1]=mod-1; gauss(); couta[p][n+1]"\n"; } return 0; }`
P4457 [BJOI2018] 治疗之雨
笔记