Submission #832127

#TimeUsernameProblemLanguageResultExecution timeMemory
832127Username4132Digital Circuit (IOI22_circuit)C++17
100 / 100
972 ms18000 KiB
#include "circuit.h" #include <iostream> #include <vector> using namespace std; using ll = long long; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) #define dforsn(i, s, n) for(int i=n-1; i>=s; --i) #define PB push_back const int MAXN = 100010, MOD = 1000002022; int n, m, he; int cal[MAXN][3]; int coef[MAXN]; int tr[2*MAXN], ax[2*MAXN]; bool lazy[MAXN]; vector<int> g[MAXN]; int crt(int x, int y, int z){ return (500001011LL*x + 143498048LL*y + 356502964LL*z)%1000002022; } ll ex(ll b, int e, int mod){ ll ret=1; while(e>0){ if(e&1) ret=(ret*b)%mod; b=(b*b)%mod; e>>=1; } return ret; } void apply(int p){ if(p<m) lazy[p]^=1; tr[p] = (ax[p] - tr[p] + MOD)%MOD; } void push(int p){ for(int s=he; s>0; --s){ int i = p>>s; if(lazy[i]){ apply(i<<1); apply(i<<1|1); lazy[i]=0; } } } void build(int p){ while(p>1){ p>>=1; int sum = (tr[p<<1] + tr[p<<1|1])%MOD; tr[p] = lazy[p]? ((ax[p] - sum + MOD)%MOD) : sum; } } void update(int l, int r){ l+=m, r+=m; int l0=l, r0=r; for(; l<r; l>>=1, r>>=1){ if(l&1) apply(l++); if(r&1) apply(--r); } build(l0); build(r0-1); } int query(int l, int r){ int ret=0; l+=m, r+=m; push(l); push(r-1); for(; l<r; l>>=1, r>>=1){ if(l&1) ret=(ret+tr[l++])%MOD; if(r&1) ret=(ret+tr[--r])%MOD; } return ret; } void dfs(int v, int mod, int prod, int cnt, int ind){ if(v>=n){ cal[v-n][ind]=cnt>0? 0 : prod; return; } int x = (int)g[v].size(); while(!(x%mod)) x/=mod, --cnt; prod = (prod*ex(x, mod-2, mod))%mod; for(int to:g[v]) dfs(to, mod, prod, cnt, ind); } void init(int N, int M, vector<int> P, vector<int> A) { n=N, m=M, he = 8*sizeof(int) - __builtin_clz(m); forn(i, n+m) g[P[i]].PB(i); vector<int> fact = {2, 223, 2242157}; forn(ind, 3){ int pr = fact[ind]; int cnt=0; ll prod=1; forn(i, n){ int x = (int)g[i].size(); while(!(x%pr)) x/=pr, cnt++; prod=(prod*x)%pr; } dfs(0, pr, prod, cnt, ind); } forn(i, m) coef[i] = crt(cal[i][0], cal[i][1], cal[i][2]); forn(i, m) ax[m+i]=coef[i]; dforsn(i, 1, m) ax[i]=(ax[i<<1]+ax[i<<1|1])%MOD; forn(i, m) if(A[i]) update(i, i+1); } int count_ways(int L, int R) { update(L-n, R+1-n); return query(0, m); }
#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...