蒟蒻刚学高消,95分求助 WA on test 15
查看原帖
蒟蒻刚学高消,95分求助 WA on test 15
107154
daduoli楼主2023/4/28 11:28

RT

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MODD=1e9+7,MAXN=5e5+10;
int n,N;
int a[MAXN],b[MAXN],band=3,inv_100,id[MAXN],cnt;
map<int,int> f[2*MAXN];
LL ksm(LL x,LL y) {
	LL res=1;
	while(y) {
		if(y&1) res=res*x%MODD;
		x=x*x%MODD;
		y>>=1;
	}
	return res;
}
LL get_c(LL x,LL y) {
	LL tmp=1;
	for(int i=x;i<=y;++i) tmp=tmp*a[i]%MODD;
	return tmp;
}
int main () {
//	freopen("sb.out","r",stdin);
//	freopen("1.out","w",stdout);
	inv_100=ksm(100,MODD-2);
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d%d",&a[i],&b[i]);
		a[i]=(LL)a[i]*inv_100%MODD;
		b[i]=(LL)b[i]*inv_100%MODD;
		if(b[i]) id[++cnt]=i;
	}
	if(!cnt) {
		cout<<get_c(1,n);
		return 0;
	}
	n=cnt;
	for(int i=1;i<=n;++i) b[i]=b[id[i]];
	N=(n+1)*2;
	f[1][1]=1;
	f[1][N+1]=1;
	for(int i=1;i<=n;++i) {
		f[(i+1)*2-1][i*2-1]=get_c(id[i-1]+1,id[i]);
		f[(i+1)*2-1][(i+1)*2-1]=MODD-1;
		f[(i+1)*2-1][(i+2)*2]=(LL)b[i]*get_c(id[i]+1,id[i+1]-1)%MODD;
		f[(i+1)*2][i*2-1]=(LL)b[i]*get_c(id[i-1]+1,id[i]-1)%MODD;
		f[(i+1)*2][(i+1)*2]=MODD-1;
		f[(i+1)*2][(i+2)*2]=get_c(id[i],id[i+1]-1);
	}
	for(int i=1;i<=N;++i) {
		if(!f[i][i]) continue;
		LL inv_a=ksm(f[i][i],MODD-2);
		for(int j=i+1;j<=min(N,i+band);++j) {
			LL rat=inv_a*f[j][i]%MODD;
			for(int q=i+1;q<=min(N,i+band);++q) {
				f[j][q]=(f[j][q]-rat*f[i][q]%MODD+MODD)%MODD;
			}
			f[j][N+1]=(f[j][N+1]-rat*f[i][N+1]%MODD+MODD)%MODD;
			f[j][i]=0;
		}
	}
	for(int i=N;i>=1;--i) {
		for(int j=i+1;j<=min(N,i+band);++j) {
			if(f[j][j]) f[i][N+1]=(f[i][N+1]-(LL)f[j][N+1]*f[i][j]%MODD+MODD)%MODD;
		}
		if(!f[i][i]) continue;
		f[i][N+1]=ksm(f[i][i],MODD-2)*f[i][N+1]%MODD;
		f[i][i]=1;
	}
	cout<<f[N-1][N+1];
	return 0;
} 
2023/4/28 11:28
加载中...