QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#49730 | #4411. Equipment Upgrade | lqhsmash | RE | 0ms | 0kb | C++20 | 3.6kb | 2022-09-22 20:38:05 | 2022-09-22 20:38:08 |
Judging History
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...