Submission #826270

#TimeUsernameProblemLanguageResultExecution timeMemory
826270alvingogoDigital Circuit (IOI22_circuit)C++17
100 / 100
949 ms27420 KiB
#include "circuit.h" #include <bits/stdc++.h> #define fs first #define sc second using namespace std; const int mod=1000002022; void add(int& x,int y){ x+=y; x-=mod*(x>=mod); } int mul(int x,int y){ return 1ll*x*y%mod; } int po(int x,int y){ int z=1; while(y){ if(y&1){ z=mul(z,x); } x=mul(x,x); y>>=1; } return z; } int inv(int x){ return po(x,222*2242156-1); } vector<int> g,a; struct ST{ struct no{ int sum=0,ans=0,tag=0; }; vector<no> st; void init(int x){ st.resize(4*x); } void upd(int v){ st[v].ans=(st[v].sum-st[v].ans+mod)%mod; st[v].tag^=1; } void pudo(int v){ if(st[v].tag){ upd(2*v+1); upd(2*v+2); st[v].tag=0; } } void pull(int v){ st[v].ans=(st[2*v+1].ans+st[2*v+2].ans)%mod; } void build(int v,int L,int R){ if(L==R){ st[v].sum=g[L]; st[v].ans=st[v].sum*a[L]; return; } int m=(L+R)/2; build(2*v+1,L,m); build(2*v+2,m+1,R); pull(v); st[v].sum=(st[2*v+1].sum+st[2*v+2].sum)%mod; } void toggle(int v,int L,int R,int l,int r){ if(L==l && r==R){ upd(v); return; } pudo(v); int m=(L+R)/2; if(r<=m){ toggle(2*v+1,L,m,l,r); } else if(l>m){ toggle(2*v+2,m+1,R,l,r); } else{ toggle(2*v+1,L,m,l,m); toggle(2*v+2,m+1,R,m+1,r); } pull(v); } int query(){ return st[0].ans; } }st; const int x[2]={2,223}; int cnt[2]={0}; int pe=1; int n,m; struct tn{ vector<int> ch; int deg=0; int cs[2]={0}; int dx=1; }; vector<tn> v; void dfs(int r,int a,int b,int c){ if(r>=n){ int z=mul(pe,inv(c)); z=mul(z,po(2,cnt[0]-a)); z=mul(z,po(223,cnt[1]-b)); g[r-n]=z; return; } for(auto h:v[r].ch){ dfs(h,a+v[r].cs[0],b+v[r].cs[1],mul(c,v[r].dx)); } } void init(int N, int M, vector<int> p, vector<int> A) { n=N; m=M; a=A; st.init(m); g.resize(m); v.resize(n+m); for(int i=1;i<n+m;i++){ v[p[i]].ch.push_back(i); v[p[i]].deg++; } for(int i=0;i<n;i++){ int s=v[i].deg; while(s%2==0){ s/=2; v[i].cs[0]++; cnt[0]++; } while(s%223==0){ s/=223; v[i].cs[1]++; cnt[1]++; } v[i].dx=s; pe=mul(pe,s); } dfs(0,0,0,1); st.build(0,0,m-1); } int count_ways(int L, int R) { st.toggle(0,0,m-1,L-n,R-n); return st.query(); }
#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...