HDU7162. Equipment Upgrade (2022杭电多校第3场1001)

题意

有一件装备，一开始是 \(0\) 级，可以强化它，当它在第 \(i\) 级时，需要花费 \(c_i\) 强化它，有 \(p_i\) 的概率强化成功（升高一级），\(1-p_i\) 的概率强化失败（降 \(1\) 至 \(i\) 级），其中降 \(j\) 级的权重为 \(w_j\)，也就是说有 \((1-p_i)\frac{w_j}{\sum\limits_{k=1}^i w_k}\) 的概率降 \(j\) 级。求从 \(0\) 级升级到 \(n\) 级的期望花费。

分析

设 \(f(i)\) 为处于第 \(i\) 级的期望代价，即要算 \(f(0)\)。

记 \(S_i=\sum\limits_{j=1}^i w_j\)

根据题意，可以写出式子

上面的式子后面的和式已经出现了卷积形式，但是不便于求解。

容易发现，上面式子包含 \(f(0),f(1),...,f(i+1)\)。稍作移项，得到

这说明如果已知 \(f(0),f(1),...,f(i)\)，就能线性地推出 \(f(i+1)\)

而现在已知 \(f(n)\) 是 \(0\)，要求 \(f(0)\)。我们可以尝试将 \(f(i)\) 线性地用 \(f(0)\) 表示，具体地说就是设

我们只要求出 \(a_i\) 和 \(b_i\)，最终答案就是 \(-\frac{b_n}{a_n}\)

根据 \(f(i)\) 的递推式和所设 \(a_i\) 与 \(b_i\) 的含义，可以推得 \(a_i\) 和 \(b_i\) 的递推式。

这样就可以CDQ分治配合卷积 \(O(n\log^2n)\) 求解 \(a_i\) 和 \(b_i\) 了。

CDQ分治的时候注意 \(w_i\) 和 \(a_j\) / \(b_j\) 贡献在了 \(a_{i+j+1}\) / \(b_{i+j+1}\) 上。调用NTT卷积时，要仔细计算好相应的位置。

代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
namespace NTT {
typedef int Lint;
typedef long long LLint;
// 2的幂次
const int maxn = (1 << 21) + 10;
const Lint mod = 998244353;
const Lint g = 3;
Lint fpow(Lint a, Lint b, Lint mod) {
    Lint res = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            res = (LLint)res * a % mod;
        a = (LLint)a * a % mod;
    }
    return res;
}
inline Lint add(Lint a, Lint b) {
    a += b;
    return a >= mod ? a - mod : a;
}
inline Lint mul(Lint a, Lint b) {
    return (LLint)a * b % mod;
}
int r[maxn];
void cal_r(int n) {
    for (int i = 0; i < n; i++) {
        r[i] = (i & 1) * (n >> 1) + (r[i >> 1] >> 1);
    }
}
void dft(Lint* a, int n, int type) {
    for (int i = 0; i < n; i++)
        if (i < r[i])
            swap(a[i], a[r[i]]);
    for (int i = 1; i < n; i <<= 1) {
        int p = i << 1;
        Lint w = fpow(g, (mod - 1) / p, mod);
        if (type == -1)
            w = fpow(w, mod - 2, mod);
        for (int j = 0; j < n; j += p) {
            Lint t = 1;
            for (int k = 0; k < i; k++, t = mul(t, w)) {
                Lint tmp = mul(a[j + k + i], t);
                a[j + k + i] = add(a[j + k], mod - tmp);
                a[j + k] = add(a[j + k], tmp);
            }
        }
    }
    if (type == -1) {
        Lint inv = fpow(n, mod - 2, mod);
        for (int i = 0; i < n; i++)
            a[i] = mul(a[i], inv);
    }
}
Lint p[maxn], q[maxn];
vector<Lint> poly_mul(const vector<Lint>& a, const vector<Lint>& b) {
    vector<Lint> res;
    int n = a.size(), m = b.size();
    res.resize(n + m - 1);
    int len = n + m - 1;
    int lim = 1;
    while (lim < len)
        lim <<= 1;
    copy(a.begin(), a.end(), p);
    fill(p + n, p + lim, 0);
    copy(b.begin(), b.end(), q);
    fill(q + m, q + lim, 0);
    cal_r(lim);
    dft(p, lim, 1), dft(q, lim, 1);
    for (int i = 0; i < lim; i++)
        p[i] = mul(p[i], q[i]);
    dft(p, lim, -1);
    for (int i = 0; i < n + m - 1; i++)
        res[i] = p[i];
    return res;
}

};  // namespace NTT

int inv(int a) {
    return NTT::fpow(a, NTT::mod - 2, NTT::mod);
}
using NTT::add;
using NTT::mod;
using NTT::mul;
using NTT::poly_mul;

int n;
const int maxn = (1 << 18) + 10;
const int inv100 = 828542813;
int lim;
int w[maxn], p[maxn], sum[maxn], inv_sum[maxn], inv_p[maxn];
int a[maxn], b[maxn], c[maxn];
void solve_ab(int l, int r) {
    if (l == r) {
        if (l == 0)
            return;
        a[l] = mul(add(a[l - 1], mod - mul(add(1, mod - p[l - 1]), mul(inv_sum[l - 1], a[l]))), inv_p[l - 1]);
        b[l] = mul(add(add(b[l - 1], mod - c[l - 1]), mod - mul(add(1, mod - p[l - 1]), mul(inv_sum[l - 1], b[l]))), inv_p[l - 1]);
        return;
    }
    int mid = l + r >> 1;
    solve_ab(l, mid);

    vector<int> P(r - l), Q(mid - l + 1);

    for (int i = 0; i < r - l; i++)
        P[i] = w[i];
    for (int i = l; i <= mid; i++)
        Q[i - l] = a[i];
    vector<int> res = poly_mul(P, Q);
    for (int i = mid + 1; i <= r; i++) {
        a[i] = add(a[i], res[i - l - 1]);
    }

    for (int i = 0; i < r - l; i++)
        P[i] = w[i];
    for (int i = l; i <= mid; i++)
        Q[i - l] = b[i];
    res = poly_mul(P, Q);
    for (int i = mid + 1; i <= r; i++) {
        b[i] = add(b[i], res[i - l - 1]);
    }
    
    solve_ab(mid + 1, r);
}
void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i] >> c[i];
        p[i] = mul(p[i], inv100);
        inv_p[i] = inv(p[i]);
    }
    for (int i = 1; i <= n - 1; i++) {
        cin >> w[i];
        sum[i] = add(sum[i - 1], w[i]);
        inv_sum[i] = inv(sum[i]);
    }
    fill(a + 1, a + 1 + n, 0);
    fill(b + 1, b + 1 + n, 0);
    solve_ab(0, n);
    cout << mul(mod - b[n], inv(a[n])) << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    a[0] = 1;
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}