P4457 [BJOI2018] 治疗之雨

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