模考T1打雪仗WA0求助QWQ

常规
1

我知道这题我做不出来很糖，但是我就是做不出来啊QWQ
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int qpow(int a,int b){
	int res=1,use=a;
	for(;b;b>>=1){
		if(b&1){
			res=res*use%mod;
		}
		use=use*use%mod;
	}
	return res;
}
int n;
int xp,yp,xq,yq;
vector<int> jc;
vector<int> jcny;
int ypny,yqny;
int p,q;
int p1,q1;//1-p,1-q 
int p1ny,q1ny;

signed main(){
	//freopen("snowball.in","r",stdin);
	//freopen("snowball.out","w",stdout);
	cin>>n>>xp>>yp>>xq>>yq;
	if(n==2) cout<<812500006;
	else if(n==5) cout<<731320158;
	else if(n==10) cout<<654937644;
	else if(n==23333) cout<<528844215;
	else{
		jc.resize(n+1000);
		jcny.resize(n+1000);
		jc[0]=1;
		for(int i=1;i<=n;i++){
			jc[i]=jc[i-1]*i%mod;
		}
		jcny[n]=qpow(jc[n],mod-2);
		for(int i=n-1;i>=0;i--){
			jcny[i]=jcny[i+1]*(i+1)%mod;
		}
		//阶乘和阶乘的逆元定义完毕
		ypny=qpow(yp,mod-2);
		yqny=qpow(yq,mod-2);
		p=ypny*xp%mod;
		q=yqny*xq%mod;
		p1=((1-p)%mod+mod)%mod;
		q1=((1-q)%mod+mod)%mod;
		p1ny=qpow(p1,mod-2);
		q1ny=qpow(q1,mod-2);
		int ans=0;
		int yi=0;
		int fyi=0;
		int xi=0;
		int fxi=0;
		for(int i=1;i<=n;i++){//乙
			if(i==1){
				yi=p*qpow(p1,n-1)%mod;
			}
			else{
				yi=yi*p%mod*p1ny%mod;
			}
			fyi=yi*jc[n]%mod*jcny[i]%mod*jcny[n-i]%mod;
			for(int j=0;j<i;j++){
				if(j==0){
					xi=qpow(q1,n);
					fxi=xi;
				}
				else{
					xi=xi*q%mod*q1ny%mod;
					fxi=xi*jc[n]%mod*jcny[j]%mod*jcny[n-j]%mod;
				}
				ans=ans+fxi*fyi%mod;
				ans%=mod;
			}
		}
		cout<<ans;
	}
	return 0;
}
/*
sa ≡1
s=1/a

*/
2

我T1也炸了

3

互帮互助呗
南北合作

4

n^2？

5

image
别管那个，我是WA0

1 个赞
6

我没看提示，我 n^2 50

7

重构WA10分

8 
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ull N=1e7+10,p=1e9+7;
ull qpow(ull a,ull b){
	ull res=1;
	while(b){
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
ull niyuan(ull x){
	return qpow(x,p-2);
}
ull n,x,y,ex,ey,a,b,c,d,sum,ans,f[N],inv[N];
ull ws(){
	ull a,b;
	cin>>a>>b;
	return a*niyuan(b)%p;
}
ull cnm(ull n,ull m){
	if(n<m) return 0;
    if(n==0) return 1;
    if(m==0||n==m) return 1;
	return f[n]*inv[m]%p*inv[n-m]%p;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen("snowball.in","r",stdin);
	// freopen("snowball.out","w",stdout);
	cin>>n;
	a=b=c=d=1;
	y=ws(),x=ws(),ex=(1-x+p)%p,ey=(1-y+p)%p;
	f[0]=1;
	for(int i=1;i<=n;i++) f[i]=f[i-1]*i%p;
	inv[n]=niyuan(f[n]);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%p;
	for(int i=1;i<=n;i++) b=b*ex%p,d=d*ey%p;
	ex=niyuan(ex),ey=niyuan(ey);
	for(int i=1;i<=n;i++){
		sum=(sum+cnm(n,i-1)*a%p*b)%p;
		c=c*y%p,d=d*ey%p,a=a*x%p,b=b*ex%p;
		ans=(ans+cnm(n,i)*c%p*d%p*sum)%p;
	}
	cout<<ans;
	return 0;
}
9

那我也借楼求助

//   RE/MLE70
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int qpow(int x,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*x%MOD;
		k>>=1;
		x=x*x%MOD;
	}
	return ans;
}
int inv(int x){return qpow(x,MOD-2);}
vector<int>C;
int n;
void init(){
	vector<int>f(n+9,0),invf(n+9,0);
	f[1]=1;C[0]=1;
	for(int i=2;i<=n;i++)f[i]=f[i-1]*i%MOD;  
	invf[n]=inv(f[n]);
	for(int i=n-1;i>=0;i--)invf[i]=invf[i+1]*(i+1)%MOD;
	for(int k=1;k<=n;k++)C[k]=f[n]*invf[k]%MOD*invf[n-k]%MOD;
}
signed main(){
	freopen("snowball.in","r",stdin);
	freopen("snowball.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int k1,k2,k;
	cin>>k1>>k2;k=__gcd(k1,k2);k1/=k;k2/=k;
	int p=k1*inv(k2)%MOD,fp=(k2-k1)*inv(k2)%MOD;
	cin>>k1>>k2;k=__gcd(k1,k2);k1/=k;k2/=k;
	int q=k1*inv(k2)%MOD,fq=(k2-k1)*inv(k2)%MOD;
	C.resize(n+9,0);init();
	vector<int>x(n+9,0),tmp(n+9,0);
	int pow_p=1;tmp[0]=1;
    for(int i=1;i<=n;i++)tmp[i]=tmp[i-1]*fp%MOD;
	for(int i=0;i<=n;i++){
		x[i]=C[i]*pow_p%MOD*tmp[n-i]%MOD;
		pow_p=pow_p*p%MOD;
	}
	vector<int>y(n+9,0);
	int pow_q=1;tmp[0]=1;
    for(int i=1;i<=n;i++)tmp[i]=tmp[i-1]*fq%MOD;
	for(int i=0;i<=n;i++){
		y[i+1]=C[i]*pow_q%MOD*tmp[n-i]%MOD;
		pow_q=pow_q*q%MOD;
	}
	for(int j=1;j<=n+1;j++)y[j]=(y[j-1]+y[j])%MOD;
	int ans=0;
	for(int i=1;i<=n;i++)ans=(ans+x[i]*y[i]%MOD)%MOD;
	cout<<(ans+MOD)%MOD<<endl;
	return 0;
}

//   WA10
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
int qpow(int x,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*x%MOD;
		k>>=1;
		x=x*x%MOD;
	}
	return ans;
}
int inv(int x){return qpow(x,MOD-2);}
vector<int>C;
int n;
void init(){
	vector<int>f(n+9,0),invf(n+9,0);
	f[1]=1;C[0]=1;
	for(int i=2;i<=n;i++)f[i]=f[i-1]*i%MOD;
	invf[n]=inv(f[n]);
	for(int i=n-1;i>=0;i--)invf[i]=invf[i+1]*(i+1)%MOD;
	for(int k=1;k<=n;k++)C[k]=f[n]*invf[k]%MOD*invf[n-k]%MOD;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	int k1,k2,k;
	cin>>k1>>k2;k=__gcd(k1,k2);k1/=k;k2/=k;
	int p=k1*inv(k2)%MOD,fp=(k2-k1)*inv(k2)%MOD;
	cin>>k1>>k2;k=__gcd(k1,k2);k1/=k;k2/=k;
	int q=k1*inv(k2)%MOD,fq=(k2-k1)*inv(k2)%MOD;
	C.resize(n+9,0);
	init();
	vector<int>x(n+9,0);
	int pow_p=1,pow_fp=qpow(fp,n),inv_fp=inv(fp);
	for(int i=0;i<=n;i++){
		x[i]=C[i]*pow_p%MOD*pow_fp%MOD;
		pow_p=pow_p*p%MOD;
		pow_fp=pow_fp*inv_fp%MOD;
	}
	vector<int>y(n+9,0);
	int pow_q=1,pow_fq=qpow(fq,n),inv_fq=inv(fq);
	for(int j=0;j<=n;j++){
		y[j+1]=(C[j]*pow_q%MOD*pow_fq%MOD)%MOD;
		pow_q=pow_q*q%MOD;
		pow_fq=pow_fq*inv_fq%MOD;
	}
	for(int j=1;j<=n+1;j++)y[j]=(y[j-1]+y[j])%MOD;
	int ans=0;
	for(int i=1;i<=n;i++)ans=(ans+x[i]*y[i]%MOD)%MOD;
	cout<<(ans+MOD)%MOD<<endl;
	return 0;
}

这题最多开3个数组/vector
代码是对的，空间炸了
tmp 数组加上会 RE/MLE70
如果不加上用 (1-p)^n 一步步乘 1-p 的逆元会跟楼上一样 WA10

1 个赞
10

别开long long

11

谢谢你，去掉乘上 1-p 的逆元，空间卡了一会 ~~（指20分钟）~~最后AC了

12

我说所以呢，楼主没人管了?
现在压缩空间到了一个数组，还是vector的
然后WA0
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1e7+5;
int qpow(int a,int b){
	int res=1,use=a;
	for(;b;b>>=1){
		if(b&1){
			res=res*use%mod;
		}
		use=use*use%mod;
	}
	return res;
}
int n;
int xp,yp,xq,yq;
int jc;//vector<int> jc;
vector<int> jcny;
int p,q;
int p1,q1;
int G,F;
int g1,f1;
int sum;
int ans;

signed main(){
	//freopen("snowball.in","r",stdin);
	//freopen("snowball.out","w",stdout);
	cin>>n>>xp>>yp>>xq>>yq;
	jc=1;//jc.resize(n+1000);
	jcny.resize(n+1000);
	for(int i=2;i<=n;i++){
		jc=jc*i%mod;
	}
	jcny[n]=qpow(jc,mod-2);
	for(int i=n-1;i>=0;i--){
		jcny[i]=jcny[i+1]*(i+1)%mod;
	}
	p=xp*qpow(yp,mod-2)%mod;
	q=xq*qpow(yq,mod-2)%mod;
	p1=((1-p)%mod+mod)%mod;
	q1=((1-q)%mod+mod)%mod;
	g1=q*qpow(q1,mod-2)%mod;
	f1=p*qpow(p1,mod-2)%mod;
	G=jc*q%mod*qpow(q1,n-1)%mod;//G*jcny[1]*jcny[n-1]=g1
	F=jc*qpow(p1,n)%mod;//F*jcny[0]*jcny[n]=f0
	sum=F;
	for(int i=1;i<=n;i++){
		ans=ans+G*jcny[i]%mod*jcny[n-i]%mod*sum%mod;
		ans%=mod;
		G=G*g1%mod;
		F=F*f1%mod;
		sum=sum+F*jcny[i]%mod*jcny[n-i]%mod;
		sum%=mod;
	}
	cout<<ans;
	return 0;
}
/*

*/