QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93914 | #4411. Equipment Upgrade | kath | RE | 0ms | 0kb | C++14 | 5.0kb | 2023-04-03 21:25:33 | 2023-04-03 21:25:36 |
Judging History
answer
#include <bits/stdc++.h>
//#define int long long
#define fp(i, a, b) for (int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = (a), i##_ = (b) - 1; i > i##_; --i)
using namespace std;
const int N = 5e4+10, P = 998244353;
using ll = long long;
using Poly = vector<int>;
#define MUL(a, b) (ll(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0) // (a += b) %= P
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P: 0) // ((a -= b) += P) %= P
Poly getInv(int L) { Poly inv(L); inv[1] = 1; fp(i, 2, L - 1) inv[i] = MUL((P - P / i), inv[P % i]); return inv; }
int POW(ll a, int b = P - 2, ll x = 1) { for (; b; b >>= 1, a = a * a % P) if (b & 1) x = x * a % P; return x; }
auto inv = getInv(N); // NOLINT
/*---------------------------------------------------------------------------*/
namespace NTT {
const int g = 3;
Poly Omega(int L) {
int wn = POW(g, P / L);
Poly w(L); w[L >> 1] = 1;
fp(i, L / 2 + 1, L - 1) w[i] = MUL(w[i - 1], wn);
fd(i, L / 2 - 1, 1) w[i] = w[i << 1];
return w;
}
auto W = Omega(1 << 20); // NOLINT
void DIF(int *a, int n) {
for (int k = n >> 1; k; k >>= 1)
for (int i = 0, y; i < n; i += k << 1)
for (int j = 0; j < k; ++j)
y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
}
void IDIT(int *a, int n) {
for (int k = 1; k < n; k <<= 1)
for (int i = 0, x, y; i < n; i += k << 1)
for (int j = 0; j < k; ++j)
x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
int Inv = P - (P - 1) / n;
fp(i, 0, n - 1) a[i] = MUL(a[i], Inv);
reverse(a + 1, a + n);
}
}
/*---------------------------------------------------------------------------*/
namespace Polynomial {
// basic operator
int norm(int n) { return 1 << (__lg(n - 1) + 1); }
void norm(Poly &a) { if (!a.empty()) a.resize(norm(a.size()), 0); else a = {0}; }
void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }
void IDFT(Poly &a) { NTT::IDIT(a.data(), a.size()); }
Poly &dot(Poly &a, Poly &b) { fp(i, 0, a.size() - 1) a[i] = MUL(a[i], b[i]); return a; }
// mul / div int
Poly &operator*=(Poly &a, int b) { for (auto &x : a) x = MUL(x, b); return a; }
Poly operator*(Poly a, int b) { return a *= b; }
Poly operator*(int a, Poly b) { return b * a; }
Poly &operator/=(Poly &a, int b) { return a *= POW(b); }
Poly operator/(Poly a, int b) { return a /= b; }
// Poly add / sub
Poly &operator+=(Poly &a, Poly b) {
a.resize(max(a.size(), b.size()));
fp(i, 0, b.size() - 1) ADD(a[i], b[i]);
return a;
}
Poly operator+(Poly a, Poly b) { return a += b; }
Poly &operator-=(Poly &a, Poly b) {
a.resize(max(a.size(), b.size()));
fp(i, 0, b.size() - 1) SUB(a[i], b[i]);
return a;
}
Poly operator-(Poly a, Poly b) { return a -= b; }
// Poly mul
Poly operator*(Poly a, Poly b) {
int n = a.size() + b.size() - 1, L = norm(n);
if (a.size() <= 8 || b.size() <= 8) {
Poly c(n);
fp(i, 0, a.size() - 1) fp(j, 0, b.size() - 1)
c[i + j] = (c[i + j] + (ll) a[i] * b[j]) % P;
return c;
}
a.resize(L), b.resize(L);
DFT(a), DFT(b), dot(a, b), IDFT(a);
return a.resize(n), a;
}
}
using namespace Polynomial;
void add(ll &x,int y){x+=y;if(x>=P)x-=P;}
void del(ll &x,int y){x-=y;if(x<0)x+=P;}
ll dp[N],pr[N],p[N],w[N],c[N];
void cdq_ntt1(int l,int r)
{
if(l==r)
{
if(l==0){dp[l]=1;return ;}
dp[l]=(P-dp[l]*(1+P-p[l-1])%P*POW(pr[l-1])%P+dp[l-1])*POW(p[l-1])%P;
return ;
}
int mid=l+r>>1;
cdq_ntt1(l,mid);
int len=mid-l+1;
Poly f(len*2+1),g(len);
for(int i=1;i<=len*2;++i)f[i]=w[i];
for(int i=0;i<len;++i)g[i]=dp[i+l];
f=f*g;
for(int i=mid+1;i<=r;++i)add(dp[i],f[i-l-1]);
cdq_ntt1(mid+1,r);
}
void cdq_ntt2(int l,int r)
{
if(l==r)
{
if(l==0)return;
dp[l]=(P-dp[l]*(1+P-p[l-1])%P*POW(pr[l-1])%P+P-c[l-1]+dp[l-1])%P*POW(p[l-1])%P;
return ;
}
int mid=l+r>>1;
cdq_ntt2(l,mid);
int len=mid-l+1;
Poly f(len*2+1),g(len);
for(int i=1;i<=len*2;++i)f[i]=w[i];
for(int i=0;i<len;++i)g[i]=dp[i+l];
f=f*g;
for(int i=mid+1;i<=r;++i)add(dp[i],f[i-l-1]);
cdq_ntt2(mid+1,r);
}
void solve()
{
int n;scanf("%d",&n);
for(int i=0;i<n;++i)scanf("%lld%lld",&p[i],&c[i]),p[i]=p[i]*POW(100)%P;
for(int i=1;i<n;++i)scanf("%lld",&w[i]);
for(int i=0;i<n;++i)pr[i]=w[i];for(int i=1;i<n;++i)add(pr[i],pr[i-1]);
for(int i=0;i<=n;++i)dp[i]=0;
cdq_ntt1(0,n);int x=dp[n];
for(int i=0;i<=n;++i)dp[i]=0;
cdq_ntt2(0,n);int y=dp[n];
printf("%lld\n",(P-y)*POW(x)%P);
}
signed main()
{
int T;scanf("%d",&T);
while(T--)solve();
}
详细
Test #1:
score: 0
Runtime Error
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...