QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93915#4411. Equipment UpgradekathAC ✓1876ms14876kbC++145.0kb2023-04-03 21:26:442023-04-03 21:26:46

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:26:46]
  • 评测
  • 测评结果:AC
  • 用时:1876ms
  • 内存:14876kb
  • [2023-04-03 21:26:44]
  • 提交

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 = 1e5+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: 100
Accepted
time: 1876ms
memory: 14876kb

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