Submission #1071049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071049		ProtonDecay314	Digital Circuit (IOI22_circuit)	C++17	100 / 100	980 ms	130820 KiB

circuit

// AM + DG
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

// I was stuck in the paradigm that I can't divide
// But, I can! It's just a matter of whether or not I can deal with a nonprime modulus
const ll MODS[4] = {2ll, 223ll, 2'242'157ll, 1'000'002'022ll};

// Fast Modular Exponentiation
ll fpw(ll base, ll pw, ll md) {
    base = base % md;
    if(pw == 0ll) return 1ll;
    ll bsqr = fpw(base * base, pw >> 1ll, md);

    return (pw & 0b1ll ? (base * bsqr) % md : bsqr);
}

// Modular Multiplicative inverse
// ! CAREFUL, only works for prime modulus
ll inv(ll base, ll md) {
    return fpw(base, md - 2ll, md);
}

// This doesn't need to be as complicated as
// your code for pre-in-post
// Only multiplication and division are required
class ModInt {
    public:
        ll m; // Mantissa, guaranteed to be nonzero
        ll pw;
        ll md;

        ModInt(ll n, ll a_md): md(a_md) {
            ll cpw = 0ll;

            while((n % md) == 0ll) {
                n /= md;
                cpw++;
            }

            m = n;
            pw = cpw;
        }

        ModInt(ll a_m, ll a_pw, ll a_md): m(a_m), pw(a_pw), md(a_md) {
            assert(m != 0ll);
            assert(a_pw >= 0ll);
        }

        ModInt operator*(const ModInt& o) const {
            return {(m * o.m) % md, pw + o.pw, md};
        }

        ModInt operator/(const ModInt& o) const {
            return {(m * inv(o.m, md)) % md, pw - o.pw, md};
        }

        // Returns this number mod the modulus
        ll to_num() const {
            return (pw == 0ll ? m % md : 0ll);
        }
};

class CRTInt {
    public:
        ModInt m1, m2, m3;

        CRTInt(ll n): m1(n, MODS[0ll]), m2(n, MODS[1ll]), m3(n, MODS[2ll]) {};

        CRTInt(ModInt a_m1, ModInt a_m2, ModInt a_m3): m1(a_m1), m2(a_m2), m3(a_m3) {}

        CRTInt operator*(const CRTInt& o) const {
            return {m1 * o.m1, m2 * o.m2, m3 * o.m3};
        }
        
        CRTInt operator/(const CRTInt& o) const {
            return {m1 / o.m1, m2 / o.m2, m3 / o.m3};
        }

        ll to_num() const {
            ll res = 0ll;

            ll f1 = fpw(MODS[1ll] * MODS[2ll], MODS[0ll] - 1ll, MODS[3ll]);
            res += m1.to_num() * f1;
            res %= MODS[3ll];

            ll f2 = fpw(MODS[0ll] * MODS[2ll], MODS[1ll] - 1ll, MODS[3ll]);
            res += m2.to_num() * f2;
            res %= MODS[3ll];

            ll f3 = fpw(MODS[0ll] * MODS[1ll], MODS[2ll] - 1ll, MODS[3ll]);
            res += m3.to_num() * f3;
            res %= MODS[3ll];

            return res;
        }
};

typedef vector<CRTInt> vci;

vvll adj;
vll a_ll;
ll n, m;

vci num_tot;
vb num_tot_vis;
CRTInt count_tot(ll i, const vvll& adj) {
    CRTInt& ans = num_tot[i];

    if(!num_tot_vis[i]) {
        ll nc = adj[i].size();
        ans = CRTInt(max(nc, 1ll));
        if(nc > 0ll) {
            for(ll j : adj[i]) {
                ans = ans * count_tot(j, adj);
            }
        }

        num_tot_vis[i] = true;
    }

    return ans;
}

vci root_path_prod;

void compute_root_path_prod(ll i, CRTInt cur_prod, const vvll& adj) {
    root_path_prod[i] = cur_prod;

    for(ll j : adj[i]) {
        compute_root_path_prod(j, cur_prod * num_tot[j], adj);
    }
}

vll contribs;

void compute_contribs(ll i, CRTInt cur_contrib, const vvll& adj) {
    // Get product of everything
    CRTInt prod_all(1ll);

    contribs[i] = cur_contrib.to_num();

    for(ll j : adj[i]) {
        prod_all = prod_all * num_tot[j];
    }

    for(ll j : adj[i]) {
        compute_contribs(j, (prod_all * cur_contrib) / num_tot[j], adj);
    }
}

class Tree {
    public:
        Tree *lt, *rt;
        ll l, r;
        ll v;
        ll nv;
        bool marked;

        Tree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(0ll), nv(0ll), marked(false) {};

        void push() {
            if(!marked) return;
            marked = false;

            if(lt == nullptr) return;

            lt->half_push();
            rt->half_push();
        }

        void half_push() {
            marked = !marked;

            swap(v, nv);
        }

        void pull() {
            v = (lt->v + rt->v) % MODS[3ll];
            nv = (lt->nv + rt->nv) % MODS[3ll];
        }

        void build(const vll& a, const vll& contribs) {
            if(l == r) {
                (a[l] == 1ll ? v : nv) = contribs[l + n];
                return;
            }

            ll m = (l + r) >> 1ll;

            lt = new Tree(l, m);
            rt = new Tree(m + 1ll, r);

            lt->build(a, contribs);
            rt->build(a, contribs);

            pull();
        }

        ll qry(ll ql, ll qr) {
            if(ql > r || qr < l) return 0ll;

            push();

            if(ql == l && qr == r) return v;

            ll m = (l + r) >> 1ll;

            return (lt->qry(ql, min(m, qr)) + rt->qry(max(m + 1ll, ql), qr)) % MODS[3ll];
        }

        void upd(ll ql, ll qr) {
            if(ql > r || qr < l) return;

            push();

            if(ql == l && qr == r) {
                half_push();
                return;
            }

            ll m = (l + r) >> 1ll;

            lt->upd(ql, min(m, qr));
            rt->upd(max(m + 1ll, ql), qr);

            pull();
        }
};

Tree* tr;

void init(int N, int M, vi P, vi A) {
    n = N; m = M;

    L(i, 0ll, N + M) {
        vll adjr;
        adj.pb(adjr);
    }

    L(i, 1ll, N + M) {
        adj[P[i]].pb(i);
    }


    num_tot.reserve(N + M);
    num_tot_vis.reserve(N + M);
    root_path_prod.reserve(N + M);
    contribs.reserve(N + M);

    L(i, 0ll, N + M) {
        num_tot.pb({1ll});
        contribs.pb(1ll);
        num_tot_vis.pb(false);
        root_path_prod.pb({1ll});
    }

    a_ll.reserve(M);

    for(int v : A) a_ll.pb((ll)v);

    count_tot(0ll, adj);

    compute_root_path_prod(0ll, CRTInt(1ll), adj);

    CRTInt prod_of_ways(1ll);


    // Compute the contributions to the sum! :))
    compute_contribs(0ll, CRTInt(1ll), adj);

    // Build the segtree
    tr = new Tree(0, m - 1ll);
    tr->build(a_ll, contribs);
}

int count_ways(int L, int R) {
    L -= n;
    R -= n;

    assert(0 <= L && L < m);
    assert(0 <= R && R < m);

    tr->upd(L, R);

    return tr->qry(0ll, m - 1ll);
}

• 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