P8493 数字电路题解

没想到转概率这个 trick 我能见到第三遍。

首先考虑如何 DP 去做这个题目。

首先令 表示 为根的子树内让点 为 的方案数。

转移是容易的，我们直接做个背包即可。

跑一次 DP 复杂度平方。我们不能接受。

不妨换个角度，我们不考虑一个取值有几个合法状态，我们考虑一个合法状态有几个取值。

首先我们注意到子树的答案相互独立，可以随意组合。每个点的取值是度数，总方案数十分好求。但是每个点度数不一定相同。

我们考虑转化成概率，这样 DP 数组里保存的就是一个 到 之间的整数。

让每个节点的阈值在 到度数之间均匀随机。我们希望求出 表示当前约束下 为 的概率。

我们发现，假设子节点中 的个数为 ，这个节点为 的概率是 。

我们要求所有情况下的概率，我们实际上要求的是 ，就是这个数的期望值。

为什么是期望值也很简单，你根据期望的定义展开，会发现是 ，就是我们要求的。

那么我们用期望的线性性展开分子上的 。

得到每个儿子 对 的贡献实际上是 。

在研究一下会发现实际上一个叶子对根接单的贡献就是这个叶子的值除掉每个祖先的度数。

线段树维护这个，支持区间反转查询整体和即可。

还有是你发现模数不是质数。反正最后要乘上一个所有非叶子度数乘积，你提前乘过来，发现每个叶子的贡献是非祖先非叶子节点的度数乘积。

维护一下即可。

▶

INFO 参考代码

#include <functional>
#include <iostream>
#include <string>
#include <vector>
#ifdef ONLINE_JUDGE
// #include "circuit.h"
#else
#include <vector>

void init(int N, int M, std::vector<int> P, std::vector<int> A);
int count_ways(int L, int R);
#endif

#ifndef ONLINE_JUDGE
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>

int main() {
    int N, M, Q;
    assert(3 == scanf("%d %d %d", &N, &M, &Q));
    std::vector<int> P(N + M), A(M);
    for (int i = 0; i < N + M; ++i) {
        assert(1 == scanf("%d", &P[i]));
    }
    for (int j = 0; j < M; ++j) {
        assert(1 == scanf("%d", &A[j]));
    }
    init(N, M, P, A);

    for (int i = 0; i < Q; ++i) {
        int L, R;
        assert(2 == scanf("%d %d", &L, &R));
        printf("%d\n", count_ways(L, R));
    }
    std::cout << std::flush;
    return 0;
}
#endif

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace maths {
template <ull mod, class int_type = ll, class uint_type = ull>
class modular {
  private:
    uint_type x;
    void norm() { x -= mod * (x >= mod); }

  public:
    modular() : x(0) {}
    modular(int_type _x) {
        if (_x < 0) {
            x = _x % (int_type)mod + (int_type)mod;
        }
        else {
            x = _x % mod;
        }
        norm();
        return;
    }
    friend modular operator+(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator-(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + mod - rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator*(const modular &lhs, const modular &rhs) {
        return modular(lhs.x * rhs.x);
    }
    modular operator-() const {
        modular ret;
        ret.x = mod - x;
        return ret;
    }
    modular operator-=(const modular &b) { return *this = *this - b; }
    modular operator+=(const modular &b) { return *this = *this + b; }
    modular operator*=(const modular &b) { return *this = *this * b; }
    bool operator==(const modular &b) const { return x == b.x; }
    uint_type val() const { return x; }
    friend std::istream &operator>>(std::istream &is, modular &rhs) {
        is >> rhs.x;
        rhs.x %= mod;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
        os << rhs.val();
        return os;
    }
};

using modint998244353 = modular<998244353>;
using modint1000000007 = modular<1000000007>;
} // namespace maths

namespace data_structure {
template <class info_t, class tag_t, class merge_info_op = std::plus<info_t>,
          class apply_op = std::multiplies<void>,
          class merge_tag_op = std::plus<tag_t>>
class lazy_segtree {
  public:
    uint n;

    const merge_info_op merge_info;
    const apply_op apply_to_info;
    const merge_tag_op merge_tag;
    const info_t id_info;
    const tag_t id_tag;
    static const size_t npos = static_cast<size_t>(-1);

    struct node {
        info_t info;
        tag_t tag;
    };

    std::vector<node> t;

  private:
    constexpr static size_t lc(const size_t &p) { return 2 * p; }
    constexpr static size_t rc(const size_t &p) { return 2 * p + 1; }

    void update(size_t p) {
        t[p].info = merge_info(t[lc(p)].info, t[rc(p)].info);
        return;
    }

    void apply_to_node(size_t p, const tag_t &tag) {
        t[p].tag = merge_tag(tag, t[p].tag);
        t[p].info = apply_to_info(tag, t[p].info);
    }

    void spread(size_t p) {
        apply_to_node(lc(p), t[p].tag);
        apply_to_node(rc(p), t[p].tag);
        t[p].tag = id_tag;
        return;
    }

    template <class input_iterator>
    input_iterator build(size_t l, size_t r, input_iterator init_val,
                         size_t p = 1) {
        t[p].info = id_info;
        t[p].tag = id_tag;
        if (l + 1 == r) {
            t[p].info = *init_val;
            init_val++;
            return init_val;
        }
        size_t mid = (l + r) / 2;
        init_val = build(l, mid, init_val, lc(p));
        init_val = build(mid, r, init_val, rc(p));
        update(p);
        return init_val;
    }

  public:
    lazy_segtree()
        : n(0), merge_info(), apply_to_info(), merge_tag(), id_info(), id_tag(),
          t() {}

    lazy_segtree(size_t _n, const merge_info_op &_merge_info = merge_info_op(),
                 const apply_op &_apply = apply_op(),
                 const merge_tag_op &_merge_tag = merge_tag_op(),
                 const info_t &_info_id = info_t(),
                 const tag_t &_tag_id = tag_t())
        : n(_n), merge_info(_merge_info), apply_to_info(_apply),
          merge_tag(_merge_tag), id_info(_info_id), id_tag(_tag_id), t(n * 4) {
        std::vector<info_t> init_val(n, id_info);
        build(0, n, init_val.begin());
    }

    template <class input_iterator>
    void assign(input_iterator iter_begin) {
        build(0, n, iter_begin);
    }

    template <class input_iterator>
    lazy_segtree(input_iterator iter_begin, input_iterator iter_end,
                 const merge_info_op &_merge_info = merge_info_op(),
                 const apply_op &_apply = apply_op(),
                 const merge_tag_op &_merge_tag = merge_tag_op(),
                 const info_t &_info_id = info_t(),
                 const tag_t &_tag_id = tag_t())
        : n(std::distance(iter_begin, iter_end)), merge_info(_merge_info),
          apply_to_info(_apply), merge_tag(_merge_tag), id_info(_info_id),
          id_tag(_tag_id), t(n * 4) {
        assign(iter_begin);
    }

    void apply(size_t l, size_t r, const tag_t &tag, size_t p = 1,
               size_t rngl = 0, size_t rngr = npos) {
        if (rngr == npos) {
            rngr = n;
        }
        if (l <= rngl && rngr <= r) {
            apply_to_node(p, tag);
            return;
        }
        size_t mid = (rngl + rngr) / 2;
        spread(p);
        if (l < mid) {
            apply(l, r, tag, lc(p), rngl, mid);
        }
        if (mid < r) {
            apply(l, r, tag, rc(p), mid, rngr);
        }
        update(p);
        return;
    }

    info_t query(size_t l, size_t r, size_t p = 1, size_t rngl = 0,
                 size_t rngr = npos) {
        if (rngr == npos) {
            rngr = n;
        }
        if (l <= rngl && rngr <= r) {
            return t[p].info;
        }
        size_t mid = (rngl + rngr) / 2;
        spread(p);
        info_t ret = id_info;
        if (l < mid) {
            ret = query(l, r, lc(p), rngl, mid); // 反正是 id。性质良好！
        }
        if (mid < r) {
            ret = merge_info(ret, query(l, r, rc(p), mid, rngr));
        }
        update(p);
        return ret;
    }

    void set(size_t pos, const info_t &info, size_t p = 1, size_t rngl = 0,
             size_t rngr = npos) {
        if (rngr == npos) {
            rngr = n;
        }
        if (rngl + 1 == rngr) {
            t[p].info = info;
            return;
        }
        size_t mid = (rngl + rngr) / 2;
        spread(p);
        if (pos < mid) {
            set(pos, info, lc(p));
        }
        else {
            set(pos, info, rc(p));
        }
        update(p);
        return;
    }
};
template <class info_t, class tag_t, class merge_info_op, class apply_op,
          class merge_tag_op>
const size_t
    lazy_segtree<info_t, tag_t, merge_info_op, apply_op, merge_tag_op>::npos;
} // namespace data_structure

namespace maths {
template <class T>
T quick_pow(T a, ull b, T id = T()) {
    T ret = id;
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) {
            ret = a * ret;
        }
    }
    return ret;
}

template <class T>
T quick_pow(T a, const std::string &s, T id = T()) {
    T ret = id;
    for (size_t i = 0; i < s.size(); i++, a = a * a) {
        if (s[i] == '1') {
            ret = a * ret;
        }
    }
    return ret;
}

} // namespace maths

namespace solve {
const uint MOD = 1'000'002'022;
using mll = maths::modular<MOD>;

struct info_t {
    mll sum;
    mll cur;

    info_t(mll _sum = 0, mll _cur = 0) : sum(_sum), cur(_cur) {}

    friend info_t operator+(const info_t &lhs, const info_t &rhs) {
        return {lhs.sum + rhs.sum, lhs.cur + rhs.cur};
    }
};

struct tag_t {
    bool flip;

    tag_t(bool _f = false) : flip(_f) {}

    friend tag_t operator+(const tag_t &lhs, const tag_t &rhs) {
        return {bool(lhs.flip ^ rhs.flip)};
    }

    friend info_t operator*(const tag_t &lhs, const info_t &rhs) {
        info_t ret = rhs;
        if (lhs.flip) {
            ret.cur = ret.sum - ret.cur;
        }
        return ret;
    }
};

struct tree {
    std::vector<std::vector<uint>> ch;
    std::vector<mll> sprod;
    std::vector<mll> val;

    void prework(uint p) {
        sprod[p] = 1;
        if (ch[p].empty()) {
            return;
        }
        for (auto &&i : ch[p]) {
            prework(i);
            sprod[p] *= sprod[i];
        }
        sprod[p] *= ch[p].size();
        return;
    }

    void dfs(uint p, mll c) {
        val[p] = c;
        std::vector<mll> pref(ch[p].size() + 1), suff(ch[p].size() + 1);
        pref[0] = 1;
        suff.back() = 1;

        for (size_t i = 0; i < ch[p].size(); i++) {
            pref[i + 1] = pref[i] * sprod[ch[p][i]];
        }

        for (int i = ch[p].size() - 1; i >= 0; i--) {
            suff[i] = suff[i + 1] * sprod[ch[p][i]];
        }

        for (size_t i = 0; i < ch[p].size(); i++) {
            dfs(ch[p][i], c * pref[i] * suff[i + 1]);
        }
        return;
    }

    tree(uint _n) : ch(_n), sprod(_n), val(_n) {}
};
} // namespace solve

data_structure::lazy_segtree<solve::info_t, solve::tag_t> seg;
solve::mll prod;
uint delta;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    delta = N;
    solve::tree t(N + M);
    for (int i = 1; i < N + M; i++) {
        t.ch[P[i]].push_back(i);
    }

    t.prework(0);
    t.dfs(0, 1);

    std::vector<solve::info_t> init(M);

    for (int i = 0; i < M; i++) {
        uint cur = N + i;
        init[i].sum = t.val[cur];
        init[i].cur = A[i] * t.val[cur];
    }

    seg.t.resize(M * 4);
    seg.n = M;
    seg.assign(init.begin());
}

int count_ways(int L, int R) {
    L -= delta;
    R -= delta;
    ++R;

    seg.apply(L, R, {true});

    return ((seg.t[1].info.cur)).val();
}