QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61366#4411. Equipment UpgradeAFewSunsWA 3813ms26856kbC++143.3kb2022-11-12 17:12:582022-11-12 17:13:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-12 17:13:00]
  • 评测
  • 测评结果:WA
  • 用时:3813ms
  • 内存:26856kb
  • [2022-11-12 17:12:58]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
#define mod 998244353
ll T,n,p[100010],c[100010],sum[100010],G[800080],g=3,rev[800080],lim=1;
struct node{
	ll x,y;
}F[800080],a[800080],b[800080];
node operator+(const node &x,const node &y){
	return (node){(x.x+y.x)%mod,(x.y+y.y)%mod};
}
node operator-(const node &x,const node &y){
	return (node){(x.x-y.x+mod)%mod,(x.y-y.y+mod)%mod};
}
node operator+(const node &x,const ll &y){
	return (node){x.x,(x.y+y)%mod};
}
node operator-(const node &x,const ll &y){
	return (node){x.x,(x.y-y+mod)%mod};
}
node operator*(const node &x,const ll &y){
	return (node){x.x*y%mod,x.y*y%mod};
}
void init(ll nn){
	lim=1;
	while(lim<(nn<<1)) lim<<=1;
	fr(i,0,lim-1) rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
}
void NTT(node *A,ll t){
	fr(i,0,lim-1) if(i<rev[i]) swap(A[i],A[rev[i]]);
	for(ll i=1;i<lim;i<<=1){
		ll Wn=my_pow(g,(mod-1)/(i<<1),mod);
		for(ll j=0;j<lim;j+=(i<<1)){
			ll w=1;
			fr(k,0,i-1){
				node tmp1=A[j+k],tmp2=A[j+k+i];
				A[j+k]=tmp1+tmp2*w;
				A[j+k+i]=tmp1-tmp2*w;
				w=w*Wn%mod;
			}
		}
	}
	if(t==-1){
		reverse(A+1,A+lim);
		ll tmp=inv(lim,mod);
		fr(i,0,lim-1) A[i]=A[i]*tmp;
	}
}
void solve(ll l,ll r){
	if(l==r){
		if(l>n||!l) return;
		F[l]=F[l]*(mod+1-p[l-1]);
		F[l]=F[l]*inv(sum[l],mod);
		F[l]=F[l-1]-c[l-1]-F[l];
		F[l]=F[l]*inv(p[l-1],mod);
		return;
	}
	ll mid=(l+r)>>1;
	solve(l,mid);
	init(r-l+1);
	fr(i,0,lim-1) a[i]=b[i]=(node){0,0};
	fr(i,l,mid) a[i-l]=F[i];
	fr(i,mid+1,r) a[i-l]=(node){0,0};
	fr(i,l,r) b[i-l]=(node){0,G[i-l]};
	NTT(a,1);
	NTT(b,1);
	fr(i,0,lim) a[i]=a[i]*b[i].y;
	NTT(a,-1);
	fr(i,mid+1,r) F[i]=F[i]+a[i-l];
	solve(mid+1,r);
}
int main(){
	T=read();
	while(T--){
		n=read();
		fr(i,0,n-1){
			p[i]=read()*inv(100,mod)%mod;
			c[i]=read();
		}
		fr(i,2,n){
			G[i]=read();
			sum[i]=(sum[i-1]+G[i])%mod;
		}
		while(lim<=n) lim<<=1;
		F[0]=(node){1,0};
		solve(0,lim-1);
		writeln((mod-F[n].y)*inv(F[n].x,mod)%mod);
		fr(i,2,n) G[i]=0;
		fr(i,0,lim-1) F[i]=(node){0,0};
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3813ms
memory: 26856kb

input:

208
2
100 41
28 64
28
3
100 48
91 13
73 3
78 92
4
100 22
15 85
26 50
41 15
90 85 77
5
100 39
51 97
83 41
4 86
36 70
49 24 17 33
6
100 53
53 45
92 2
36 40
61 61
76 52
18 37 75 49 96
7
100 5
21 47
39 58
78 1
82 93
59 82
56 90
1 41 76 64 84 27
8
100 14
38 77
66 20
1 63
47 47
3 12
87 16
99 62
14 81 75 2...

output:

375
243619761
141260443
912990775
435041270
858243909
809396215
906670540
468990423
760114239
896346643
75552067
392967826
937237239
41764863
808244774
953249376
474825424
772239270
364947886
212546170
747513284
797146579
171590060
914943013
589016656
161551325
619517373
450910035
568404322
96962203...

result:

wrong answer 4th lines differ - expected: '516768753', found: '912990775'