QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#93914#4411. Equipment UpgradekathRE 0ms0kbC++145.0kb2023-04-03 21:25:332023-04-03 21:25:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-03 21:25:36]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-04-03 21:25:33]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: