IOI2022 D2T1 数字电路（计数&概率/组合数学+线段树区间翻转）

本文链接：https://blog.csdn.net/Code92007/article/details/127721693

题目

n+m(n,m<=1e5)个点的有根树，点号[0,n+m-1]，根为0号点

其中，[0,n-1]是分支节点（非叶子节点），[n,n+m-1]是叶子结点

初始时，第i个叶子节点有一个状态值ai，来自输入，0/1，表示门是否开启

而对于分支节点j来说，设其直连儿子有son[j]个，则其状态值可以从[1,son[j]]里指定

比如，指定其状态值为3，则表示，当至少有3个直连儿子的门开启时，当前门才开启

q(q<=1e5)次更新，

每次更新输入两个参数l、r(n<=l<=r<=n+m-1)，

表示翻转叶子结点所在的一段区间的状态值，

每次更新后询问，使得0号点的门能开启的，安排分支节点的状态值的方案数

答案对1e9+2022取模

思路来源

IOI2022 数字电路 - Nastia - 博客园

题解

不直接统计方案数，统计出现合法方案的概率

dp[i]表示只考虑i子树时，i这扇门能开启的概率

根据概率的线性可加性， $dp[i]=\frac{1}{|son[i]|}\sum_{j \in son[i]}dp[j]$

合法的方案数=合法的概率*总方案数，

而总方案数=每个节点独立决策之积， $\prod_{i}|son[i]|$

叶子节点的子树大小为1，不妨也乘进去

而对于叶子节点来说，dp[i]=a[i]，即完全由初始值0/1决定

独立考虑每一个叶子的贡献，

发现其在被转移到根的时候，在这条路径上的每个点x都乘以了1/|son[x]|，

而最后乘以总方案数的时候，所有点x的|son[x]|都乘上去了，

一消之后发现，叶子x节点的贡献是，不在0和x这条路径上的所有点的|son|的乘积

于是，相当于每个叶子节点x都有一个固定的值b[x]，

需要维护q次翻转操作，a[x]=0时x的贡献是0，a[x]=1时x的贡献是b[x]

因此，只需线段树区间翻转维护区间和，相当于每个节点维护一个s0、维护一个s1，

翻转时交换s0、s1，并打上待交换子树的lazy标记即可

心得

~~cls推荐的题，说是cf1800，我估计了一下至少有2300~~

看似维护动态dp，实则动态dp完全不可做

于是又是计数典中典，考虑每个点的贡献

代码

代码来自于思路来源

#include <bits/stdc++.h>
#define debug(...) std::cerr<<#__VA_ARGS__<<" : "<<__VA_ARGS__<<std::endl

#include "circuit.h"

using ll = long long;

const int maxn = 200005;
const ll mod = 1000002022;
int N, M;
bool lzy[maxn << 2];
ll fac[maxn], a[maxn], s0[maxn << 2], s1[maxn << 2];
std::vector<int> G[maxn], A;

void dfs(int pos) {
    if (G[pos].empty()) {
        fac[pos] = 1ll;
        return;
    }

    fac[pos] = (ll)G[pos].size();

    for (auto nxt : G[pos]) {
        dfs(nxt);
        (fac[pos] *= fac[nxt]) %= mod;
    }
}

void dfs2(int pos, ll now) {
    if (G[pos].size() == 0) {
        a[pos] = now;
        return;
    }

    std::vector<ll> pre(G[pos].size(), 1ll), suf(G[pos].size(), 1ll);

    for (int i = 0; i < (int)G[pos].size(); i++) {
        if (i)
            (pre[i] *= pre[i - 1]) %= mod;

        (pre[i] *= fac[G[pos][i]]) %= mod;
    }

    for (int i = (int)G[pos].size() - 1; ~i; i--) {
        if (i != (int)G[pos].size() - 1)
            (suf[i] *= suf[i + 1]) %= mod;

        (suf[i] *= fac[G[pos][i]]) %= mod;
    }

    for (int i = 0; i < (int)G[pos].size(); i++) {
        dfs2(G[pos][i], now * (i - 1 >= 0 ? pre[i - 1] : 1ll) % mod * (i + 1 < (int)G[pos].size() ? suf[i + 1] : 1ll)
             % mod);
    }
}

void pushup(int pos) {
    s0[pos] = (s0[pos << 1] + s0[pos << 1 | 1]) % mod;
    s1[pos] = (s1[pos << 1] + s1[pos << 1 | 1]) % mod;
}

void pushdown(int pos) {
    if (lzy[pos]) {
        lzy[pos << 1] ^= 1;
        std::swap(s0[pos << 1], s1[pos << 1]);
        lzy[pos << 1 | 1] ^= 1;
        std::swap(s0[pos << 1 | 1], s1[pos << 1 | 1]);
        lzy[pos] = 0;
    }
}

void build(int pos, int lef, int rig, const int &n) {
    if (lef == rig) {
        if (A[lef - 1] == 0)
            s0[pos] = a[lef - 1 + n];
        else
            s1[pos] = a[lef - 1 + n];
    } else {
        int mid = lef + rig >> 1;
        build(pos << 1, lef, mid, n);
        build(pos << 1 | 1, mid + 1, rig, n);
        pushup(pos);
    }
}

void update(int l, int r, int pos = 1, int lef = 1, int rig = M) {
    if (l <= lef && rig <= r) {
        lzy[pos] ^= 1;
        std::swap(s0[pos], s1[pos]);
    } else if (l <= rig && r >= lef) {
        pushdown(pos);
        int mid = lef + rig >> 1;
        update(l, r, pos << 1, lef, mid);
        update(l, r, pos << 1 | 1, mid + 1, rig);
        pushup(pos);
    }
}

void init(int n, int m, std::vector<int> p, std::vector<int> a) {
    A = a;

    for (int i = 1; i < (int)p.size(); i++)
        G[p[i]].push_back(i);

    dfs(0);
    dfs2(0, 1ll);
    build(1, 1, M = m, N = n);
}

int count_ways(int l, int r) {
    update(l - N + 1, r - N + 1);
    return s1[1];
}
/*
int main() {
    init(3, 4, {-1, 0, 1, 2, 1, 1, 0}, {1, 0, 1, 0});
    debug(count_ways(3, 4));
    debug(count_ways(4, 5));
    debug(count_ways(3, 6));
    return 0;
}
*/