Submission #784211

#	Time	Username	Problem	Language	Result	Execution time	Memory
784211		oscar1f	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1014 ms	27332 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

struct noeud{
    ll give0,give1,coeff,deb,fin;
};

const ll TAILLE_MAX=300*1000+5,MODU=1000*1000*1000+2022,NB_FACT=3;
ll nbSom,nbSource,rep;
pair<ll,ll> prodGlob[NB_FACT];
vector<ll> pere,prem;
vector<ll> etatDeb;
pair<ll,ll> prodSom[TAILLE_MAX][NB_FACT];
ll nbFils[TAILLE_MAX];
ll valMod;
ll val[TAILLE_MAX];
noeud cumu[TAILLE_MAX];

pair<ll,ll> decompo(ll nb,ll p) {
    if (nb==0) {
        return {1,0};
    }
    ll nbOccu=0;
    while (nb%p==0) {
        nbOccu++;
        nb/=p;
    }
    return {nb%p,nbOccu};
}

ll puis(ll nb,ll expo,ll p) {
    if (expo==0) {
        return 1;
    }
    ll ans=puis(nb,expo/2,p);
    ans*=ans;
    ans%=p;
    if (expo%2==1) {
        ans*=nb;
        ans%=p;
    }
    return ans;
}

ll inverse(ll nb,ll p) {
    return puis(nb,p-2,p);
}

void prepa(ll pos,ll debInter,ll finInter) {
    cumu[pos].deb=debInter;
    cumu[pos].fin=finInter;
    if (debInter==finInter) {
        cumu[pos].give0=val[debInter]%MODU;
    }
    else {
        ll midInter=(debInter+finInter)/2;
        prepa(2*pos,debInter,midInter);
        prepa(2*pos+1,midInter+1,finInter);
        cumu[pos].give0=(cumu[2*pos].give0+cumu[2*pos+1].give0)%MODU;
    }
}

void pushFlag(ll pos) {
    if (cumu[pos].coeff%2==1) {
        swap(cumu[pos].give0,cumu[pos].give1);
    }
    if (cumu[pos].deb!=cumu[pos].fin) {
        cumu[2*pos].coeff+=cumu[pos].coeff;
        cumu[2*pos].coeff%=2;
        cumu[2*pos+1].coeff+=cumu[pos].coeff;
        cumu[2*pos+1].coeff%=2;
    }
    cumu[pos].coeff=0;
}

pair<ll,ll> update(ll pos,ll debInter,ll finInter) {
    //cout<<pos<<" "<<debInter<<" "<<finInter<<" : ";
    if (cumu[pos].deb>finInter or cumu[pos].fin<debInter) {
        //cout<<"A"<<endl;
        pushFlag(pos);
        return {cumu[pos].give0,cumu[pos].give1};
    }
    if (cumu[pos].deb>=debInter and cumu[pos].fin<=finInter) {
        //cout<<"B"<<endl;
        cumu[pos].coeff++;
        pushFlag(pos);
        return {cumu[pos].give0,cumu[pos].give1};
    }
    //cout<<"C"<<endl;
    pushFlag(pos);
    auto gauche=update(2*pos,debInter,finInter);
    auto droite=update(2*pos+1,debInter,finInter);
    cumu[pos].give0=(gauche.first+droite.first)%MODU;
    cumu[pos].give1=(gauche.second+droite.second)%MODU;
    return {cumu[pos].give0,cumu[pos].give1};
}

void afficher() {
    cout<<endl;
    for (ll i=1;i<20;i++) {
        cout<<i<<" : "<<cumu[i].deb<<" "<<cumu[i].fin<<" "<<cumu[i].coeff<<" "<<cumu[i].give0<<" "<<cumu[i].give1<<endl;
    }
    cout<<endl;
}

void init(int N, int M, vector<int> P, vector<int> A) {
    nbSom=N;
    nbSource=M;
    for (ll i:P) {
        pere.push_back(i);
    }
    prem={2,223,MODU/(2*223)};
    for (ll i:A) {
       etatDeb.push_back(i);
    }
    for (ll i:pere) {
        if (i>=0) {
            nbFils[i]++;
        }
    }
    for (ll j=0;j<NB_FACT;j++) {
        prodGlob[j].first=1;
        for (ll i=0;i<nbSom;i++) {
            prodGlob[j].first*=decompo(nbFils[i],prem[j]).first;
            prodGlob[j].first%=prem[j];
            prodGlob[j].second+=decompo(nbFils[i],prem[j]).second;
        }
    }

    for (ll j=0;j<NB_FACT;j++) {
        prodSom[0][j]=decompo(nbFils[0],prem[j]);
        for (ll i=1;i<nbSom+nbSource;i++) {
            prodSom[i][j]=prodSom[pere[i]][j];
            prodSom[i][j].first*=decompo(nbFils[i],prem[j]).first;
            prodSom[i][j].first%=prem[j];
            prodSom[i][j].second+=decompo(nbFils[i],prem[j]).second;
        }
    }

    /*for (ll i=0;i<nbSom+nbSource;i++) {
        cout<<i<<" : ";
        for (ll j=0;j<NB_FACT;j++) {
            cout<<prodSom[i][j].first<<" "<<prodSom[i][j].second<<"   ";
        }
        cout<<endl;
    }*/
    /*for (int j=0;j<NB_FACT;j++) {
        cout<<prodGlob[j].first<<" "<<prodGlob[j].second<<endl;
    }*/

    for (ll i=0;i<nbSource;i++) {
        //cout<<i+nbSom<<" : ";
        for (ll j=0;j<NB_FACT;j++) {
            if (prodSom[i+nbSom][j].second<prodGlob[j].second) {
                valMod=0;
            }
            else {
                valMod=prodGlob[j].first*inverse(prodSom[i+nbSom][j].first,prem[j]);
                //cout<<prodGlob[j].first<<" "<<prodSom[i+nbSom][j].first<<" "<<valMod<<" "<<prem[j]<<endl;
                valMod%=prem[j];
            }
            //cout<<valMod<<" ";
            val[i]+=valMod*(((MODU/prem[j])*inverse((MODU/prem[j]),prem[j]))%MODU);
        }
        val[i]%=MODU;
        //cout<<endl;
    }

    prepa(1,0,nbSource-1);
    //afficher();

    for (ll i=0;i<nbSource;i++) {
        //cout<<i+nbSom<<" : "<<val[i]<<endl;
        if (etatDeb[i]==1) {
            rep=update(1,i,i).second;
            //afficher();
        }
    }
}

int count_ways(int L, int R) {
    L-=nbSom;
    R-=nbSom;
    rep=update(1,L,R).second;
    return rep%MODU;
}

• 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