DDOSvoid's Blog

2022杭电多校3 A Equipment Upgrade

发表于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7162

简要题意：数轴上有 $n + 1$ 个点，分别为 $[0,n]$，你现在在 $0$，从 $i$ 走到 $i+1$ 需要花费 $c_i$ 的时间，有 $p_i$ 的成功概率，$(1-p_i)\frac{w_j}{\sum_{k=1}^iw_k}$ 的概率走到 $i-j(1\le j\le i)$，求走到 $n$ 的期望时间

$n\le 10^5$

Solution

令 $f_i$ 为从 $i$ 走到 $n$ 的概率，容易得到转移为 $f_i=c_i+p_if_{i+1}+\frac{1-p_i}{\sum_{j=1}^iw_j}\sum_{j=0}^{i-1}f_jw_{i-j}$

注意到后面的 $sum$ 很像是一个分治 $NTT$ 的形式，但是注意到我们的转移成环，但是对于这个形式，我们可以简单移项解决，我们可以得到 $f_{i+1}=\frac{1}{p_i}(f_i-c_i-\frac{1-p_i}{\sum_{j=1}^iw_j}\sum_{j=0}^{i-1}f_jw_{i-j})$，同时我们已知 $f_n=0$，要求 $f_0$，那么我们可以设 $f_i=a_if_0+b_i$，注意到 $a_i$ 和 $b_i$ 之间没有联系，可以直接拆成两个式子，这两个式子都是分治 $NTT$ 的形式，直接做即可

时间复杂度 $O(n\log^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 998244353;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}
inline int add(int a, int b) { return (a += b) >= p ? a -= p : a; }
inline int mul(int a, int b) { return 1ll * a * b % p; } 

typedef std::vector<int> Poly;
namespace Pol {
 
    const int N = 4200000;
    int a[N], b[N];
 
    int P[N];
    void init_P(int n) {
        int l = 0; while ((1 << l) < n) ++l;
        for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
    }
    void NTT(int *a, int n, int type) {
        static int w[N]; ll G = 3, Gi = pow_mod(G, p - 2);
        for (int i = 0; i < n; ++i) if (i < P[i]) swap(a[i], a[P[i]]);
        for (int i = 2, m = 1; i <= n; m = i, i *= 2) {
            int wn = pow_mod(type > 0 ? G : Gi, (p - 1) / i);
            w[0] = 1; for (int j = 1; j < m; ++j) w[j] = mul(wn, w[j - 1]);
            for (int j = 0; j < n; j += i)
                for (int k = 0; k < m; ++k) {
                    int t1 = a[j + k], t2 = mul(a[j + k + m], w[k]);
                    a[j + k] = add(t1, t2);
                    a[j + k + m] = add(t1, p - t2);
                }
        }
        if (type < 0) {
            ll inv = pow_mod(n, p - 2);
            for (int i = 0; i < n; ++i) a[i] = inv * a[i] % p;
        }
    }
    Poly Mul(const Poly &A, const Poly &B, int n1, int n2) {
        int n = 1; while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        for (int i = 0; i < n1; ++i) a[i] = add(A[i], p);
        for (int i = 0; i < n2; ++i) b[i] = add(B[i], p);
        fill(a + n1, a + n, 0), fill(b + n2, b + n, 0);
        NTT(a, n, 1); NTT(b, n, 1);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
        NTT(a, n, -1); Poly ans(n1 + n2 - 1); copy_n(a, n1 + n2 - 1, ans.begin());
        return ans;
    }
    Poly MMul(const Poly &A, const Poly &B, int len) { //减法卷积
        int n = 1; while (n < 2 * len - 1) n <<= 1; init_P(n);
        for (int i = 0; i < len; ++i) a[i] = add(A[i], p);
        for (int i = 0; i < len; ++i) b[i] = add(B[i], p);
        fill(a + len, a + n, 0), fill(b + len, b + n, 0); reverse(b, b + len);
        NTT(a, n, 1); NTT(b, n, 1);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
        NTT(a, n, -1); Poly ans(len);
        copy_n(a, len, ans.begin()); reverse(ans.begin(), ans.end());
        return ans;
    }
}  // namespace Pol

int n;

ll pr[maxn], c[maxn], w[maxn], s[maxn], invs[maxn], invpr[maxn]; 
void solve(int opt, Poly &A, const Poly &B, int l, int r) {
    if (l + 1 == r) {
        if (l > 0) {
            A[l] = 1ll * A[l] * add(1, p - pr[l - 1]) % p * invs[l - 1] % p;
            A[l] = add(A[l - 1], p - A[l]);
            if (opt) A[l] = add(A[l], p - c[l - 1]);
            A[l] = 1ll * A[l] * invpr[l - 1] % p;
        }
        return ;
    } int m = l + r >> 1; solve(opt, A, B, l, m); 
    Poly t1(m - l), t2(r - l);
    for (int i = l; i < m; ++i) t1[i - l] = A[i];
    for (int i = 0; i < r - l; ++i) t2[i] = B[i];
    Poly t = Pol::Mul(t1, t2, m - l, r - l);
    for (int i = m; i < r; ++i)
        if (i + 1 < n + 1) A[i + 1] = (A[i + 1] + t[i - l]) % p;
    solve(opt, A, B, m, r); 
}

void work() {
    cin >> n; ll inv100 = pow_mod(100, p - 2), ansa, ansb;
    for (int i = 0; i < n; ++i) cin >> pr[i] >> c[i], pr[i] = pr[i] * inv100 % p;
    for (int i = 1; i < n; ++i) cin >> w[i], s[i] = add(s[i - 1], w[i]);
    for (int i = 1; i < n; ++i) invs[i] = pow_mod(s[i], p - 2); 
    for (int i = 0; i < n; ++i) invpr[i] = pow_mod(pr[i], p - 2);
    
    Poly A(n + 1), B(n + 1); A[0] = 1; 
    for (int i = 1; i < n; ++i) B[i] = w[i];
    solve(0, A, B, 0, n + 1); ansa = A[n];
    
    fill(A.begin(), A.end(), 0);
    solve(1, A, B, 0, n + 1); ansb = A[n];

    cout << p - ansb * pow_mod(ansa, p - 2) % p << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}