IOI2022 数字电路

第一次体验当年IOI的题（虽然是Day2的签到）

这题有一个经典的套路——在一些计数DP题，我们不直接统计方案数，而是统计出现合法方案的概率。

这样我们设\(dp(i)\)表示子树\(i\)内部，让节点\(i\)为\(1\)的方案数，则\(dp(i)=\frac{1}{|son_{i}|}\sum_{j\in son_{i} } dp(j)\)，最后总方案就是\(dp(0)\times \prod |son_{i}|\)。如果叶子节点初始值为\(1\)，则\(dp(i)=1\)；否则\(dp(i)=0\)。

考虑一个叶子节点是\(1\)时对方案数的贡献，不难发现从一个叶子到根节点路径上所有点都要乘上\(\frac{1}{|son_{i}|}\)，最后还要乘上\(\prod |son_{i}|\)，那么消一下就可以发现，一个叶子的贡献是\(\prod_{i,i不在叶子到根的路径上\;\;\;\;\;\;\;\;\;\;\;\;\;\;} |son_{i}|\)。

那么这个可以通过求每个节点儿子的前缀后缀积，做到\(O(n)\)求出每个叶子的贡献。

对于区间反转，那么我们可以用一个线段树+懒标记求出当前标号为\(1\)的叶子的贡献和。

时间复杂度为\(O(q\log n)\)。

#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;
}
*/