Submission #1158292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158292		Math4Life2020	디지털 회로 (IOI22_circuit)	C++20	100 / 100	503 ms	42348 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll MOD = 1e9+2022;
const ll Nm = 131072; const ll E = 17;
const ll p1 = 2; const ll p2 = 223;
const ll DMAX = 2e6;
ll exp01[DMAX]; ll exp02[DMAX];
//array form: {vp1, vp2, rest}

void gexp() {
    exp01[0]=1;
    exp02[0]=1;
    for (ll i=1;i<DMAX;i++) {
        exp01[i]=(exp01[i-1]*p1)%MOD;
        exp02[i]=(exp02[i-1]*p2)%MOD;
    }
}

ll inv(ll x) {
    //cout << "inverse of x="<<x<<" is ";
    array<ll,3> a = {x,1,0};
    array<ll,3> b = {MOD,0,1};
    while (a[0]!=0) {
        if (a[0]>b[0]) {
            swap(a,b);
        } else {
            ll k = b[0]/a[0];
            for (ll i=0;i<3;i++) {
                b[i]-=k*a[i];
            }
        }
    }
    ll y = b[1];
    ll RVAL = (y+2*MOD+MOD*((-y)/MOD))%MOD;
    //cout << RVAL<<"\n";
    return RVAL;
}

array<ll,3> gform(ll x) {
    array<ll,3> a0 = {0,0,0};
    while (x%p1==0) {
        a0[0]++;
        x=x/p1;
    }
    while (x%p2==0) {
        a0[1]++;
        x=x/p2;
    }
    a0[2]=x;
    return a0;
}

ll eval(array<ll,3> a1) {
    return (((exp01[a1[0]]*exp02[a1[1]])%MOD)*a1[2])%MOD;
}

array<ll,3> d(array<ll,3> a1, array<ll,3> a2) { //a1/a2
    return {a1[0]-a2[0],a1[1]-a2[1],(a1[2]*inv(a2[2]))%MOD};
}

array<ll,3> m(array<ll,3> a1, array<ll,3> a2) {
    return {a1[0]+a2[0],a1[1]+a2[1],(a1[2]*a2[2])%MOD};
}

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

ll tval;
ll N,M;
ll iwt[Nm]; //initial weights
ll stw0[2*Nm]; //sum of total weights segtree
ll sts[2*Nm]; //sum of active segtree
bool lz[2*Nm]; //lazy tag HAS BEEN APPLIED to current vertex

void lft(ll p) {
    if (p>=Nm || lz[p]) {
        return;
    }
    sts[p]=(sts[2*p]+sts[2*p+1])%MOD;
}

void pdn(ll p) {
    if (p>=Nm || !lz[p]) {
        return;
    }
    sts[2*p]=(stw0[2*p]-sts[2*p]+MOD)%MOD;
    lz[2*p]=1-lz[2*p];
    sts[2*p+1]=(stw0[2*p+1]-sts[2*p+1]+MOD)%MOD;
    lz[2*p+1]=1-lz[2*p+1];
    lz[p]=0;
}

ll updP(ll p) {
    for (ll e=E;e>=0;e--) {
        pdn(p>>e);
    }
    sts[p]=(stw0[p]-sts[p]+MOD)%MOD;
    lz[p]=1-lz[p];
    for (ll e=0;e<=E;e++) {
        lft(p>>e);
    }
    return sts[p];
}

ll upd(ll l, ll r) {
    if (l>r) {
        return 0;
    }
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        return (updP((l>>vl)+(1<<(E-vl)))+upd(l+(1<<vl),r))%MOD;
    } else {
        return (updP((r>>vr)+(1<<(E-vr)))+upd(l,r-(1<<vr)))%MOD;
    }
}

void init(int _N, int _M, vector<int> P, vector<int> A) {
    N = _N; M = _M;
    gexp();
    vector<ll> fdeg(N,0);
    array<ll,3> tstr = {0,0,1};
    array<ll,3> cstr[N];
    for (ll t=1;t<(N+M);t++) {
        fdeg[P[t]]++;
    }
    tstr=gform(fdeg[0]);
    cstr[0]=d((array<ll,3>){0,0,1},tstr);
    for (ll t=1;t<N;t++) {
        array<ll,3> cpt = gform(fdeg[t]);
        //cout << "cpt at t="<<t<<" is "<<cpt[0]<<","<<cpt[1]<<","<<cpt[2]<<"\n";
        tstr = m(tstr,cpt);
        cstr[t]=d(cstr[P[t]],cpt);
        //cout << "cstr[P[t]]="<<cstr[P[t]][0]<<","<<cstr[P[t]][1]<<","<<cstr[P[t]][2]<<"\n";
        //cout << "cstr at t="<<t<<" is "<<cstr[t][0]<<","<<cstr[t][1]<<","<<cstr[t][2]<<"\n";
    }
    for (ll t=N;t<(N+M);t++) {
        iwt[t-N]=eval(m(cstr[P[t]],tstr));
        //cout << "iwt["<<(t-N)<<"]="<<iwt[t-N]<<"\n";
    }
    tval = eval(tstr);
    for (ll i=0;i<Nm;i++) {
        stw0[i+Nm]=iwt[i];
        sts[i+Nm]=0;
        lz[i+Nm]=0;
    }
    for (ll p=(Nm-1);p>=0;p--) {
        stw0[p]=(stw0[2*p]+stw0[2*p+1])%MOD;
        sts[p]=0;
        lz[p]=0;
    }
    for (ll i=0;i<M;i++) {
        if (A[i]==0) {
            upd(i,i);
        }
    }
}

int count_ways(int L, int R) {
    upd(L-N,R-N);
    return (tval-sts[1]%MOD+MOD)%MOD;
}

• 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