QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49730#4411. Equipment UpgradelqhsmashRE 0ms0kbC++203.6kb2022-09-22 20:38:052022-09-22 20:38:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-22 20:38:08]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-09-22 20:38:05]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MOD = 998244353;

void show (vector<int> a) {
    for (int x : a) cerr << x << ' ';
    cerr << endl;
}

int fpow (int x, int p) {
    int res = 1;
    for (; p; p >>= 1, x = (ll)x * x % MOD)
        if (p & 1) res = (ll)res * x % MOD;
    return res;
}

const int N = 1e5 + 50;
const int G = 3;
const int Gi = fpow (G, MOD - 2);
int T, n, w[N], p[N], sum[N], ip[N], c[N];

void ntt (vector<int>& f, int inv, vector<int> rev, int lim) {
    for (int i = 0; i < lim; i ++ ) 
        if (i > rev[i]) swap (f[i], f[rev[i]]);
    for (int k = 1; k < lim; k <<= 1 ){
        int wn = fpow (inv == 1 ? G : Gi, (MOD - 1) / (k << 1));
        for (int i = 0; i < lim; i += k << 1) {
            int w = 1;
            for (int j = 0; j < k; j ++, w = (ll)w * wn % MOD) {
                int nx = f[i + j], ny = (ll)w * f[i + j + k] % MOD;
                f[i + j] = (nx + ny) % MOD;
                f[i + j + k] = (nx - ny + MOD) % MOD;
            }
        }
    }
    if (inv == 1) return ;
    int len = fpow (lim, MOD - 2);
    for (int i = 0; i < lim; i ++) f[i] = (ll)f[i] * len % MOD;
}

vector<int> mul (vector<int> a, vector<int> b) {
    int n = a.size (), m = b.size (), lim, bit;
    for (lim = 1, bit = 0; lim <= n + m - 1; lim <<= 1) bit ++;
    vector<int> rev (lim, 0);
    a.resize (lim), b.resize (lim);
    for (int i = n; i < lim; i ++) a[i] = 0;
    for (int i = m; i < lim; i ++) b[i] = 0;
    for (int i = 0; i < lim; i ++) 
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    ntt (a, 1, rev, lim), ntt (b, 1, rev, lim);
    for (int i = 0; i < lim; i ++) a[i] = (ll)a[i] * b[i] % MOD;
    ntt (a, -1, rev, lim);
    return a.resize (n + m - 1), a;
}

vector<int> f1, g1, f2, g2, a, b;

void CDQNTT (int l, int r) {
    if (l == r) {
        if (l == 0) return ;
        f2[r + 1] = (f2[r] - (1ll - p[r] + MOD) * sum[r] % MOD * f1[r] % MOD + MOD) * ip[r] % MOD;
        g2[r + 1] = (g2[r] - c[r] + MOD - (1ll - p[r] + MOD) * sum[r] % MOD * g1[r] % MOD + MOD) * ip[r] % MOD;
        return ;
    }
    int mid = (l + r) >> 1;
    CDQNTT (l, mid);

    a = vector<int> (mid - l + 1, 0);
    b = vector<int> (r - l, 0);
    for (int i = l; i <= mid; i ++) a[i - l] = f2[i];
    for (int i = 1; i <= r - l; i ++) b[i - 1] = w[i];
    a = mul (a, b);
    for (int i = mid + 1; i <= r; i ++)     
        f1[i] = (f1[i] + a[i - l - 1]) % MOD;

    a = vector<int> (mid - l + 1, 0);
    b = vector<int> (r - l, 0);
    for (int i = l; i <= mid; i ++) a[i - l] = g2[i];
    for (int i = 1; i <= r - l; i ++) b[i - 1] = w[i];
    a = mul (a, b);
    for (int i = mid + 1; i <= r; i ++)     
        g1[i] = (g1[i] + a[i - l - 1]) % MOD;

    CDQNTT (mid + 1, r);
}

int main () {
    scanf ("%d", &T);
    while (T --) {
        scanf ("%d", &n);
        for (int i = 0; i < n; i ++) scanf ("%d%d", &p[i], &c[i]);
        for (int i = 1; i < n; i ++) scanf ("%d", &w[i]);
        for (int i = 1; i < n; i ++) sum[i] = (sum[i - 1] + w[i]) % MOD;
        for (int i = 1; i <= n; i ++) sum[i] = fpow (sum[i], MOD - 2);
        for (int i = 0; i < n; i ++) p[i] = fpow (100, MOD - 2) * (ll)p[i] % MOD;
        for (int i = 0; i < n; i ++) ip[i] = fpow (p[i], MOD - 2);

        f1 = g1 = f2 = g2 = vector<int> (n + 1, 0);
        f2[0] = 1, g2[0] = 0;
        f2[1] = 1, g2[1] = (MOD - c[0]) % MOD;
        CDQNTT (0, n);

        int ans = (MOD - g2[n]) * (ll)fpow (f2[n], MOD - 2) % MOD;
        printf("%d\n", (ans % MOD + MOD) % MOD);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

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: