Digital Circuit

Per-gate counting For each threshold gate i with c_i inputs, if exactly k of its inputs output 1, then exactly (k, c_i) choices of p_i make gate i output 1, and c_i - (k, c_i) make it output 0. Aggregation with genera...

Updated May 21, 2026

Track IOI

Year 2022

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

A digital circuit has $N$ threshold gates (numbered $0,\ldots,N{-}1$) and $M$ source gates (numbered $N,\ldots,N{+}M{-}1$). Gate 0 is the output. Each non-root gate has a unique parent (a threshold gate). Every threshold gate $i$ with $c_i$ inputs has a parameter $p_i \in [1, c_i]$: the gate outputs 1 iff at least $p_i$ of its inputs are 1.

Source gates have binary states. After each update (toggling source gates in a contiguous range $[L, R]$), count the number of parameter assignments that make gate 0 output 1, modulo $10^9 + 22$.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution

Per-gate counting

For each threshold gate $i$ with $c_i$ inputs, if exactly $k$ of its inputs output 1, then exactly $\min(k, c_i)$ choices of $p_i$ make gate $i$ output 1, and $c_i - \min(k, c_i)$ make it output 0.

Aggregation with generating polynomials

For each gate $i$, define:

\begin{align*}\mathrm{ways\_on}[i] &= \text{number of parameter assignments in the subtree of } i \text{ making } i \text{ output 1,}\\ \mathrm{ways\_off}[i] &= \text{the complementary count.} \end{align*}

For a source gate $s$: $\mathrm{ways\_on}[s] = \text{state}(s)$ and $\mathrm{ways\_off}[s] = 1 - \text{state}(s)$.

For a threshold gate $i$ with children $g_1, \ldots, g_{c_i}$, we accumulate two quantities over the children:

\begin{align*}A &= \prod_j \bigl(\mathrm{ways\_on}[g_j] + \mathrm{ways\_off}[g_j]\bigr),\\ B &= \sum_{\text{subsets }S} |S| \cdot \prod_{j \in S} \mathrm{ways\_on}[g_j] \cdot \prod_{j \notin S} \mathrm{ways\_off}[g_j]. \end{align*}

Then $\mathrm{ways\_on}[i] = B$ and $\mathrm{ways\_off}[i] = c_i \cdot A - B$.

The pair $(A, B)$ can be maintained incrementally. Writing $\mathrm{tot}_j = \mathrm{ways\_on}[g_j] + \mathrm{ways\_off}[g_j]$, the transition when appending child $g_{j+1}$ is

\begin{align*}A' &= A \cdot \mathrm{tot}_{j+1},\\ B' &= B \cdot \mathrm{tot}_{j+1} + A \cdot \mathrm{ways\_on}[g_{j+1}]. \end{align*}

Handling toggle updates

When source gates in $[L,R]$ are toggled, the values $\mathrm{ways\_on}$ and $\mathrm{ways\_off}$ change for all ancestors. A full bottom-up recomputation takes $O(N + M)$ per update.

Lemma.

The total work per update is $O(N + M)$ since each gate is recomputed at most once in the bottom-up pass.

For full-score performance, one can factor each gate's contribution as a product of per-source-gate affine functions and maintain these products under range toggles using a segment tree with lazy propagation. We present the simpler $O((N+M)Q)$ recomputation below.

Complexity

Initialization: $O(N + M)$.
Per update (above code): $O(N + M)$ for full recomputation.
Per update (optimized): $O(N + M + \log M)$ using a segment tree over source gates that maintains the product of affine contributions and supports range-toggle with lazy propagation.
Space: $O(N + M)$.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000002022;

int N, M;
vector<int> parent_gate;
vector<vector<int>> children;
vector<int> source_state;

// For each threshold gate: number of inputs
vector<int> num_inputs;

// Precomputed: for each threshold gate i,
// the "coefficient" of each source gate's on/off state
// This is complex for general trees.

// Simple approach: recompute from scratch each time
ll ways_on_val, ways_off_val; // for gate 0

void recompute() {
    vector<ll> ways_on(N + M), ways_off(N + M);

    // Source gates
    for (int i = N; i < N + M; i++) {
        if (source_state[i - N]) {
            ways_on[i] = 1;
            ways_off[i] = 0;
        } else {
            ways_on[i] = 0;
            ways_off[i] = 1;
        }
    }

    // Process threshold gates bottom-up
    for (int i = N - 1; i >= 0; i--) {
        ll A = 1, B = 0;
        int ci = children[i].size();
        for (int ch : children[i]) {
            ll total = (ways_on[ch] + ways_off[ch]) % MOD;
            ll newA = A * total % MOD;
            ll newB = (B * total + A % MOD * ways_on[ch]) % MOD;
            A = newA;
            B = newB;
        }
        ways_on[i] = B % MOD;
        ways_off[i] = ((ll)ci * A % MOD - B % MOD + MOD) % MOD;
    }

    ways_on_val = ways_on[0];
}

void init(int _N, int _M, vector<int> P, vector<int> A) {
    N = _N; M = _M;
    parent_gate = P;
    source_state = A;
    children.resize(N + M);
    num_inputs.resize(N, 0);

    for (int i = 1; i < N + M; i++) {
        children[P[i]].push_back(i);
        if (P[i] < N) num_inputs[P[i]]++;
    }
}

int count_ways(int L, int R) {
    // Toggle source gates L..R (0-indexed from N)
    for (int i = L; i <= R; i++)
        source_state[i - N] ^= 1;

    recompute();
    return (int)(ways_on_val % MOD);
}

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    vector<int> P(n + m), A(m);
    P[0] = -1;
    for (int i = 1; i < n + m; i++) scanf("%d", &P[i]);
    for (int i = 0; i < m; i++) scanf("%d", &A[i]);
    init(n, m, P, A);
    while (q--) {
        int L, R;
        scanf("%d %d", &L, &R);
        printf("%d\n", count_ways(L, R));
    }
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/2022/circuit/solution.texC++ implementationcompetitive_programming/ioi/2022/circuit/solution.cpp