Submission #1183818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183818		gyg	Digital Circuit (IOI22_circuit)	C++20	4 / 100	344 ms	11264 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector 
const int N = 1e5 + 5, M = 1e5 + 5, MD = 1000002022;

int n, m;
arr<vec<int>, N + M> ch;
arr<int, N + M> on;

int md(int x) { return (x + MD) % MD; }
arr<arr<int, 2>, N + M> dp;
arr<arr<int, 4>, N + M> kn;

void upd(int u) {
    if (u >= n + 1) {
        dp[u][0] = (on[u]) ? 0 : 1;
        dp[u][1] = (on[u]) ? 1 : 0;
        return;
    }
    int k = ch[u].size();
    kn[0][0] = 1;
    for (int i = 1; i <= k; i++) {
        int v = ch[u][i - 1];
        for (int c = 0; c <= k; c++) {
            int lv = md(dp[v][0] * kn[i - 1][c]);
            int tk = (c == 0) ? 0 : md(dp[v][1] * kn[i - 1][c - 1]);
            kn[i][c] = md(lv + tk);
        }
    }

    dp[u][0] = dp[u][1] = 0;
    for (int c = 0; c <= k; c++) {
        dp[u][0] = md(dp[u][0] + (k - c) * kn[k][c]);
        dp[u][1] = md(dp[u][1] + c * kn[k][c]);
    }
}

void init(sig _n, sig _m, vec<sig> _pr, vec<sig> _on) {
    n = _n, m = _m;
    for (int u = 2; u <= n + m; u++) {
        int pr = _pr[u - 1] + 1;
        ch[pr].push_back(u);
    }
    for (int u = n + 1; u <= n + m; u++)
        on[u] = _on[u - n - 1];

    for (int u = n + m; u >= 1; u--)
        upd(u);
}

arr<bool, N + M> lzy;
void prp(int u) {
    if (!lzy[u]) return;
    for (int v : ch[u])
        swap(dp[v][0], dp[v][1]), lzy[v] = true;
    lzy[u] = false;
}
void dfs(int l, int r, int u = 1, int lw = n + 1, int hg = n + m) {
    // cout << l << " " << r << ": " << lw << " " << hg << '\n';
    if (l <= lw && hg <= r) {
        swap(dp[u][0], dp[u][1]), lzy[u] = true;
        return;
    }
    prp(u);
    int md = (lw + hg) / 2;
    if (l <= md) dfs(l, r, 2 * u, lw, md);
    if (r > md) dfs(l, r, 2 * u + 1, md + 1, hg);
    upd(u);
}

sig count_ways(sig l, sig r) {
    l++, r++;
    dfs(l, r);
    return dp[1][1];
}

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