Submission #832121

#TimeUsernameProblemLanguageResultExecution timeMemory
832121Username4132디지털 회로 (IOI22_circuit)C++17
46 / 100
3030 ms7496 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 PB push_back const int MAXN = 100010; int n, m, arr[MAXN]; int cal[MAXN][3]; int coef[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 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; 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) arr[i]=A[i]; } int count_ways(int L, int R) { forsn(i, L-n, R+1-n) arr[i]^=1; ll sum=0; forn(i, m) sum+=arr[i]*coef[i]; return sum%1000002022; }
#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...