QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#819922 | #4411. Equipment Upgrade | Kevin5307 | AC ✓ | 4228ms | 18704kb | C++23 | 4.6kb | 2024-12-18 18:21:06 | 2024-12-18 18:21:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace Polynomial
{
using ll=long long;
using poly=vector<ll>;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
inline int sz(const poly &p)
{
return p.size();
}
const poly operator +(const poly &a,const poly &b)
{
int p=sz(a),q=sz(b);
int n=max(p,q);
poly ret(n,0);
for(int i=0;i<n;i++)
{
if(i<p) ret[i]+=a[i];
if(i<q) ret[i]+=b[i];
if(ret[i]>=mod) ret[i]-=mod;
}
return ret;
}
const poly operator -(const poly &a,const poly &b)
{
int p=sz(a),q=sz(b);
int n=max(p,q);
poly ret(n,0);
for(int i=0;i<n;i++)
{
if(i<p) ret[i]+=a[i];
if(i<q) ret[i]+=mod-b[i];
if(ret[i]>=mod) ret[i]-=mod;
}
return ret;
}
poly operator *(poly a,poly b)
{
const ll g=3;
int len=sz(a)+sz(b);
int m=1;
while(m<sz(a)+sz(b)) m*=2;
a.resize(m);
b.resize(m);
vector<int> rev(m);
for(int i=0;i<m;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)*(m>>1));
for(int i=0;i<m;i++)
if(rev[i]<i)
{
swap(a[i],a[rev[i]]);
swap(b[i],b[rev[i]]);
}
for(int i=1;i<m;i<<=1)
{
ll gn=ksm(g,(mod-1)/i/2);
for(int j=0;j<m;j+=(i<<1))
{
ll g0=1;
for(int k=0;k<i;k++,g0=g0*gn%mod)
{
{
ll x=a[j+k],y=g0*a[i+j+k]%mod;
a[j+k]=(x+y)%mod;
a[i+j+k]=(x+mod-y)%mod;
}
{
ll x=b[j+k],y=g0*b[i+j+k]%mod;
b[j+k]=(x+y)%mod;
b[i+j+k]=(x+mod-y)%mod;
}
}
}
}
for(int i=0;i<m;i++)
a[i]=a[i]*b[i]%mod;
for(int i=0;i<m;i++)
if(rev[i]<i)
swap(a[i],a[rev[i]]);
for(int i=1;i<m;i<<=1)
{
ll gn=ksm(g,(mod-1)/i/2*(mod-2));
for(int j=0;j<m;j+=(i<<1))
{
ll g0=1;
for(int k=0;k<i;k++,g0=g0*gn%mod)
{
ll x=a[j+k],y=g0*a[i+j+k]%mod;
a[j+k]=(x+y)%mod;
a[i+j+k]=(x+mod-y)%mod;
}
}
}
ll val=ksm(m,mod-2);
for(int i=0;i<m;i++)
a[i]=a[i]*val%mod;
a.resize(len-1);
return a;
}
poly inv(poly p,int deg)
{
p.resize(deg);
if(deg==1) return {ksm(p[0],mod-2)};
poly w=inv(p,(deg+1)/2);
poly g=w+w-p*w*w;
g.resize(deg);
return g;
}
poly deriv(poly p)
{
for(int i=0;i<sz(p);i++)
p[i]=p[i]*i%mod;
p.erase(p.begin());
return p;
}
poly integ(poly p)
{
p.insert(p.begin(),0);
for(int i=0;i<sz(p);i++)
p[i]=p[i]*ksm(i,mod-2)%mod;
return p;
}
poly ln(poly p)
{
return integ(deriv(p)*inv(p,sz(p)));
}
poly exp(poly p,int deg)
{
p.resize(deg);
if(deg==1)
return {1};
poly g=exp(p,(deg+1)/2);
g=g*(poly{1}-ln(g)+p);
g.resize(deg);
return g;
}
const poly operator %(poly a,poly b)
{
if(sz(a)<sz(b)) return a;
int n=sz(a),m=sz(b);
int d=n-m+1;
poly a2=a,b2=b;
reverse(a2.begin(),a2.end());
reverse(b2.begin(),b2.end());
a2.resize(d);
b2.resize(d);
poly q=a2*inv(b2,d);
q.resize(d);
reverse(q.begin(),q.end());
q=a-b*q;
q.resize(m-1);
return q;
}
const poly operator /(poly a,poly b)
{
if(sz(a)<sz(b)) return a;
int n=sz(a),m=sz(b);
int d=n-m+1;
poly a2=a,b2=b;
reverse(a2.begin(),a2.end());
reverse(b2.begin(),b2.end());
a2.resize(d);
b2.resize(d);
poly q=a2*inv(b2,d);
q.resize(d);
reverse(q.begin(),q.end());
return q;
}
}
using namespace Polynomial;
int p[100100],c[100100];
ll inv100=ksm(100,mod-2);
ll f[100100],g[100100];
ll x[100100],y[100100];
ll w[100100];
ll psum[100100];
void solve(int l,int r)
{
if(l==r)
{
ll inv=ksm(psum[l],mod-2);
ll X=x[l]*inv%mod;
ll Y=y[l]*inv%mod;
ll P=p[l]*inv100%mod;
f[l+1]=(f[l]-(mod+1-P)*X-c[l])%mod;
if(f[l+1]<0) f[l+1]+=mod;
g[l+1]=(g[l]-(mod+1-P)*Y)%mod;
if(g[l+1]<0) g[l+1]+=mod;
ll invp=ksm(P,mod-2);
f[l+1]=f[l+1]*invp%mod;
g[l+1]=g[l+1]*invp%mod;
return ;
}
int mid=(l+r)/2;
solve(l,mid);
poly A(mid-l+1),B(mid-l+1),C(r-l+1);
for(int i=l;i<=mid;i++)
A[i-l]=f[i];
for(int i=l;i<=mid;i++)
B[i-l]=g[i];
for(int i=1;i<=r-l;i++)
C[i]=w[i];
A=A*C;
B=B*C;
for(int i=mid+1;i<=r;i++)
{
x[i]=(x[i]+A[i-l])%mod;
y[i]=(y[i]+B[i-l])%mod;
}
solve(mid+1,r);
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i]>>c[i];
for(int i=1;i<n;i++)
cin>>w[i];
for(int i=1;i<n;i++)
psum[i]=(psum[i-1]+w[i])%mod;
for(int i=0;i<=n;i++)
f[i]=g[i]=x[i]=y[i]=0;
f[0]=0;
g[0]=1;
solve(0,n-1);
cout<<(mod-f[n])*ksm(g[n],mod-2)%mod<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4228ms
memory: 18704kb
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 516768753 850749960 897481401 602765935 510391586 689398435 784190268 697129546 505176530 687991734 16121189 684750916 616413796 324645467 60836964 997265902 829124402 135215114 115586183 566051860 45973142 577302112 438599189 808712026 903587073 180745041 931933480 429669755...
result:
ok 208 lines