Submission #810905

#	Time	Username	Problem	Language	Result	Execution time	Memory
810905		jophyyjh	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1036 ms	32700 KiB

circuit

/**
 * I nearly fully-solved this problem in IOI 2022, though I ran out of time. Initially, I
 * was only hoping to score more partials, but it turned out to be a full solution.
 * 
 * For [S1-3], DFS + dp suffice: for each node u in the tree, we compute dp1[u], the num of
 * different assignments of parameters to threshold gates in the subtree of u that will
 * result in u being 1. Similarly, we can define dp0[u].
 * Let v_1, v_2, ..., v_k be all the children of u. Mathematically,
 *      dp1[u] = (dp1[v_1] * dp1[v_2] * ... * dp1[v_k]) * k      <-- k options for u
 *                      -->   + (dp1[v_1] * ... * dp1[v_{k-1}] * dp0[v_k])
 *  (k-1) options for u -->   +  ...
 *                      -->   +  dp0[v_1] * dp1[v_2] * ... * dp1[v_k]) * (k-1)
 *              + ...,
 * and dp0[u] can be found from dp1[u]. 
 * 
 * The huge sum can be computed quite efficiently, again with dp. For each node u, let
 * partial[i] (0 <= i <= k) be
 *    sum{ (dp0[v_1] or dp1[v_1]) * ... * (dp0[v_k] or dp1[v_k]) : exactly i dp1[]'s }.
 * We can find each partial[i] iteratively:
 *         partial[i] <-- partial[i] * dp0[some_v] + partial[i-1] * dp1[some_v].
 * Therefore, dp1[u] = partial[1] * 1 + ... + partial[k] * k. So, O((N+M)^2 * Q). [S4] can
 * be solved too, because we only have to update O(log(N)) dp1[]'s and dp0[]'s in each
 * query.
 * 
 * I thought there must be ways to optimize this dp. Because the source gates can receive
 * arbitrary input, I tried out some examples; for each one of them, I use a variable to
 * denote each source gate and try to find the expression for each gate on paper. I noticed
 * a pattern, but didn't bother to prove it in the contest. Anyway, let's begin.
 * Let f(x) = (dp1[v_1] * x + dp0[v_1])...(dp1[v_k] * x + dp0[v_k]), then
 * partial[i] = coefficient of x^i in f(x). Write f(x) as c_0 + c_1 * x + ... + c_k * x^k.
 * We have
 *          f'(x) = 1 * c_1 + 2 * c_2 * x + 3 * c_3 * x^2 + ... + k * c_k * x^{k-1},
 * which means
 *      dp[u] = c_1 + 2 * c_2 + ... + k * c_k
 *            = f'(1)
 *            = sum{ dp1[v_i] * prod{ (dp1[v_j] + dp0[v_j]) : j != i }  : 1 <= i <= k }
 *            = sum{ dp[v_i] * prod{ sub[v_j] : j != i } }.
 * Here, sub[v] is the num of comb of freely choosing all thresholds in the subtree of v.
 * This quantity can be easily found with DFS. The trick is pretty well-known, at least
 * in the Olympiad maths circle.
 * 
 * After doing some more examples on my scratch paper, I noticed that the formula we
 * obtained above implies that dp[1] is a linear combination of
 * dp[N], dp[N+1], ..., dp[N+M-1], i.e. the inputs. Nice! It remains to compute the
 * coefficient of each input in the final linear comb of dp[1], and use
 * a segment tree with lazy propagation.
 * 
 * Overall, I'd say this is a pretty interesting problem, at least with the parts of dp & 
 * maths. The portion of handling queries with seg tree + lazy is definitely a bit
 * mechanical, but still tests a contestant's data structure skills. Note that the MOD is
 * not a prime! Therefore, dp[u] cannot be sum{ dp[v_i] / sub[v_i] } * prod{ sub[v_i] },
 * cuz a multiplicative inverse may not exist under mod 1000002022. The issue can be
 * resolved by computing the suffix product and prefix product of sub[].
 * 
 * Time Complexity: O(N + (M + Q) * log(M))         (Full solution)
 * Implementation 1                 (DP, maths, segment tree, lazy propagation)
*/

#include <bits/stdc++.h>
#include "circuit.h"

typedef long long   ll;
typedef std::vector<int>  vec;

const ll MOD = 1000002022;


// Our toggleable linear combination segment tree (using lazy propagation) (lol)
class TogLincomb {
private:
    int m;
    std::vector<ll> pre_coeff;
    std::vector<ll> tree;
    std::vector<bool> lazy;     // whether the range has been lazily toggled
    inline void flip(int k, int i, int j) {
        tree[k] = (pre_coeff[j + 1] - pre_coeff[i]) - tree[k], lazy[k] = 1 - lazy[k];
        tree[k] = (tree[k] % MOD + MOD) % MOD;
    }
    inline void push(int k, int i, int j) {
        if (lazy[k]) {
            int mid = (i + j) / 2;
            flip(2 * k, i, mid);
            flip(2 * k + 1, mid + 1, j);
        }
        lazy[k] = false;
    }
    void _toggle(int l, int r, int k, int i, int j) {
        if (i > r || l > j || l > r)
            return;
        if (i == l && j == r) {
            flip(k, i, j);
            return;
        }
        int mid = (i + j) / 2;
        push(k, i, j);
        _toggle(l, std::min(r, mid), 2 * k, i, mid);
        _toggle(std::max(l, mid + 1), r, 2 * k + 1, mid + 1, j);
        tree[k] = tree[2 * k] + tree[2 * k + 1], tree[k] %= MOD;
    }
public:
    TogLincomb()    {}
    TogLincomb(int size, const std::vector<ll>& coeff) {
        m = size;
        pre_coeff.assign(m + 1, 0);
        for (int k = 0; k < m; k++)
            pre_coeff[k + 1] = pre_coeff[k] + coeff[k], pre_coeff[k + 1] %= MOD;
        tree.assign(4 * m, 0);
        lazy.assign(4 * m, false);
    }
    void toggle(int l, int r)   { _toggle(l, r, 1, 0, m - 1); }
    ll sum()    { return tree[1]; }
};

int n;
std::vector<vec> tree;
std::vector<ll> dp, sub;
TogLincomb seg_tree;

void pre_comp(int k) {
    sub[k] = 1;
    if (k >= n)
        return;
    for (int child : tree[k]) {
        pre_comp(child);
        sub[k] *= sub[child], sub[k] %= MOD;
    }
    sub[k] *= int(tree[k].size()), sub[k] %= MOD;
}

void compute(int k) {
    int c = tree[k].size();
    std::vector<ll> prefix(c + 1), suffix(c + 1);
    prefix[0] = suffix[c] = 1;
    for (int i = 0, j = c - 1; i < c; i++, j--) {
        prefix[i + 1] = prefix[i] * sub[tree[k][i]] % MOD;
        suffix[j] = suffix[j + 1] * sub[tree[k][j]] % MOD;
    }
    for (int i = 0; i < c; i++) {
        int child = tree[k][i];
        dp[child] = dp[k] * prefix[i] % MOD * suffix[i + 1] % MOD;
        compute(child);
    }
}

void init(int N, int m, vec P, vec A) {
    n = N;
    tree.assign(n + m, vec());
    for (int k = 1; k < n + m; k++)
        tree[P[k]].push_back(k);
    
    sub.resize(n + m);
    pre_comp(0);
    dp.resize(n + m);
    dp[0] = 1;
    compute(0);
    seg_tree = TogLincomb(m, std::vector<ll>(dp.begin() + n, dp.end()));
    for (int k = 0; k < m; k++) {
        if (A[k])
            seg_tree.toggle(k, k);
    }
}

int count_ways(int l, int r) {
    seg_tree.toggle(l - n, r - n);
    return int(seg_tree.sum());
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11