This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |