#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 2e5 + 1;
const int MOD = 1000002022;
vector<ll> grafo[MAXN];
ll val[MAXN];
ll n, m, tot = 0;
pair<ll, ll> dfs(ll nod) { // fr: ways activo (state=1), se: ways apagado (state=0)
if (nod >= n) {
return {val[nod], 1 - val[nod]};
}
vector<pair<ll, ll>> children_ways;
for (auto k : grafo[nod]) {
auto p = dfs(k);
children_ways.pb(p);
}
int c = sz(children_ways);
if (c == 0) {
return {0, 0};
}
vector<ll> S(c);
for (int i = 0; i < c; i++) {
S[i] = (children_ways[i].fr + children_ways[i].se) % MOD;
}
// Productos prefijo (left: prod j=0 to i-1)
vector<ll> left(c);
left[0] = 1;
for (int i = 1; i < c; i++) {
left[i] = left[i - 1] * S[i - 1] % MOD;
}
// Productos sufijo (right: prod j=i+1 to c-1)
vector<ll> right(c);
right[c - 1] = 1;
for (int i = c - 2; i >= 0; i--) {
right[i] = right[i + 1] * S[i + 1] % MOD;
}
// Calcular on
ll onn = 0;
for (int i = 0; i < c; i++) {
ll prod_others = left[i] * right[i] % MOD;
onn = (onn + children_ways[i].fr * prod_others % MOD) % MOD;
}
// Calcular full_prod = prod all S
ll full_prod = 1;
for (auto s : S) {
full_prod = full_prod * s % MOD;
}
// off = c * full_prod - onn
ll off = ((ll)c * full_prod % MOD - onn + MOD) % MOD;
return {onn, off};
}
void calc() {
pair<ll, ll> a = dfs(0);
tot = a.fr;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
ll i;
for (i = 1; i < sz(P); i++)
grafo[P[i]].pb(i);
for (i = 0; i < sz(A); i++)
val[i + N] = A[i];
n = N;
m = M;
}
int count_ways(int L, int R) {
ll i;
for (i = L; i <= R; i++)
val[i] = !val[i];
calc();
return tot;
}
# | 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... |