Submission #784130

#TimeUsernameProblemLanguageResultExecution timeMemory
784130oscar1fDigital Circuit (IOI22_circuit)C++17
2 / 100
456 ms5660 KiB
#include "circuit.h" #include<bits/stdc++.h> using namespace std; #define ll long long const ll TAILLE_MAX=200*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]; 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 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<nbSource;i++) { for (ll j=0;j<NB_FACT;j++) { if (prodSom[i][j].second<prodGlob[j].second) { valMod=0; } else { valMod=prodGlob[j].first*inverse(prodSom[i][j].first,prem[j]); } val[i]+=valMod*(((MODU/prem[j])*inverse((MODU/prem[j]),prem[j]))%MODU); } val[i]%=MODU; } for (int i=0;i<nbSource;i++) { rep+=etatDeb[i]*val[i]; rep%=MODU; } } int count_ways(int L, int R) { L-=nbSom; R-=nbSom; for (int i=L;i<=R;i++) { if (etatDeb[i]==0) { rep+=val[i]; } else { rep-=val[i]-MODU; } rep%=MODU; etatDeb[i]=1-etatDeb[i]; } return rep; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...