#include "circuit.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("-avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000002022;
vector<pair<ll, ll>>a;
vector<int>P;
vector<int>A;
vector<vector<int>>c;
int N, M;
vector<bool> F(200009, false);
vector<int> L, R;
void calc(int i)
{
int d = c[i].size();
vector<ll> k(d + 2, 0ll);
ll v = 1;
a[i] = {0ll, 0ll};
for (int j : c[i])
{
int v0 = a[j].first;
int v1 = a[j].second;
if (F[j])
swap(v0, v1);
ll a1_ = 0;
ll a0_ = 0;
a1_ = a[i].second * (v0 + v1) + v * v1;
a0_ = a[i].first * (v0 + v1) + v * v0;
a[i].first = a0_;
a[i].second = a1_;
v *= (v0 + v1);
a[i].first %= mod;
a[i].second %= mod;
v %= mod;
}
}
void init(int N_, int M_, vector<int> P_, vector<int> A_) {
P = P_;
A = A_;
N = N_;
M = M_;
a = vector<pair<ll, ll>>(N + M);
c = vector<vector<int>>(N + M);
L = vector<int>(N + M);
R = vector<int>(N + M);
for (int i = 1; i < N + M; i++)
c[P[i]].push_back(i);
for (int i = N + M - 1; i >= N; i--)
{
if (A[i - N] == 1)
a[i] = {0, 1};
else
a[i] = {1, 0};
L[i] = R[i] = i;
}
for (int i = N - 1; i >= 0; i--)
{
calc(i);
L[i] = N + M + 5;
R[i] = -1;
for (int j : c[i])
{
L[i] = min(L[i], L[j]);
R[i] = max(R[i], R[j]);
}
}
}
int count_ways(int X, int Y) {
function<void(int)>f = [&](int i)->void
{
if (R[i] < X || Y < L[i])
return;
if (X <= L[i] && R[i] <= Y)
{
F[i] = F[i] ^ true;
}
else
{
for (int j : c[i])
{
F[j] = F[j] ^ F[i];
f(j);
}
calc(i);
F[i] = false;
}
};
f(0);
if (F[0])
return a[0].first;
return (int)a[0].second;
}
Compilation message
cc1plus: error: attribute '-avx2' argument 'target' is unknown
