QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61366 | #4411. Equipment Upgrade | AFewSuns | WA | 3813ms | 26856kb | C++14 | 3.3kb | 2022-11-12 17:12:58 | 2022-11-12 17:13:00 |
Judging History
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'