#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define int long long
using namespace std ;
const int maxn = 1e6 + 10 , inf = 1e9+ 10 , mod = 1000002022 ;
int a[maxn] , n ,m , ans[maxn];
vector <int >G[maxn] ;
int sb[maxn] ;
void dfs2(int v){
sb[v] =1 ;
if(v < n)sb[v] = sz(G[v]) ;
for(int u : G[v]){
dfs2(u) ;
sb[v] = sb[v] * sb[u] % mod ;
}
}
void dfs(int v , int z =1 ){
vector <int> pr , sf;
pr.pb(1);
for(int u : G[v]){
pr.pb(sb[u]) ;
sf.pb(sb[u]) ;
};
sf.pb(1);
rep(i , 1 ,sz(pr)-1){
pr[i] = pr[i-1] * pr[i] % mod ;
}
per(i , sz(sf)-2 , 0){
sf[i] = sf[i+1] * sf[i] % mod ;
}
if(v >= n)ans[v-n] = z ;
int c =0 ;
for(int u : G[v]){
dfs(u , z * pr[c] % mod * sf[c+1] % mod) ;
c++ ;
}
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
n = N ;
m = M ;
rep(i ,1, n+m-1){
G[P[i]].pb(i) ;
}
dfs2(0);
dfs(0) ;
rep(i , 0 ,m-1)a[i] = A[i] ;
}
int32_t count_ways(int32_t L, int32_t R) {
int sm =0 ;
rep(i , L-n , R-n){
a[i] ^= 1;
}
rep(i , 0 ,m-1){
if(a[i] == 1)sm= (sm + ans[i]) % mod ;
}
return sm;
}
# | 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... |