This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "circuit.h"
const ll MOD = 1000002022;
VL contr;
struct SEGTREE {
int n;
VL tree1, tree2;
VI lazy;
SEGTREE(){}
SEGTREE(VI val) {
n = 1;
while (n < val.size()) n *= 2;
tree1 = tree2 = VL(2*n);
lazy = VI(2*n);
rep(i, val.size()) {
if (val[i]) tree1[i + n-1] = contr[i];
else tree2[i + n-1] = contr[i];
}
build(0, 0, n-1);
}
void build(int N, int L, int R) {
if (L == R) return;
int M = (L + R) / 2;
build(2*N+1, L, M);
build(2*N+2, M+1, R);
tree1[N] = (tree1[2*N+1] + tree1[2*N+2]) % MOD;
tree2[N] = (tree2[2*N+1] + tree2[2*N+2]) % MOD;
}
void push(int N) {
if (lazy[N]%2) swap(tree1[N], tree2[N]);
if (2*N+2 < 2*n) {
lazy[2*N+1] += lazy[N];
lazy[2*N+2] += lazy[N];
}
lazy[N] = 0;
}
void upd(int N, int L, int R, int l, int r) {
push(N);
if (R < l || L > r) return;
if (l <= L && R <= r) {
lazy[N]++;
push(N);
return;
}
int M = (L + R) / 2;
upd(2*N+1, L, M, l, r);
upd(2*N+2, M+1, R, l, r);
tree1[N] = (tree1[2*N+1] + tree1[2*N+2]) % MOD;
tree2[N] = (tree2[2*N+1] + tree2[2*N+2]) % MOD;
}
void upd(int l, int r) {
upd(0, 0, n-1, l, r);
}
ll get() {
return tree1[0];
}
void print() {
return;
rep(u, 2*n-1) {
cout << tree1[u] << " ";
if (set<int>{0, 2, 6, 14, 30}.count(u)) cout << endl;
}
rep(u, 2*n-1) {
cout << tree2[u] << " ";
if (set<int>{0, 2, 6, 14, 30}.count(u)) cout << endl;
}
rep(u, 2*n-1) {
cout << lazy[u] << " ";
if (set<int>{0, 2, 6, 14, 30}.count(u)) cout << endl;
}
cout << "-------------------------------" << endl;
}
} seg;
bool test6;
int n, sz;
VVI gp;
VI val;
VL dpa; // sev
VL dpb; // spitak
VI depth;
void dfs2(int u = 0) {
for (int v : gp[u]) {
depth[v] = depth[u]+1;
dfs2(v);
}
}
void init(int N, int M, VI P, VI A) {
n = N + M;
sz = M;
gp = VVI(n);
rep(u, n) if (u) gp[P[u]].pb(u);
val = VI(n);
rep(u, M) val[u+N] = A[u];
depth = VI(n);
test6 = true;
rep(u, N) if (gp[u].size() != 2) test6 = false;
if (test6) {
/*cout << "TEST 6" << endl;*/
dfs2();
contr = VL(n);
VL twopow(n+1);
twopow[0] = 1;
replr(i, 1, n) twopow[i] = twopow[i-1]*2 % MOD;
rep(u, n) contr[u] = twopow[N - depth[u]];
seg = SEGTREE(val);
/*for (ll x : contr) cout << x << " "; cout << endl;*/
/*cout << "-------------------------------" << endl;*/
/*seg.print();*/
}
}
VL subsets(VL& a, VL& b) {
int n = a.size();
VVL dp(n+1, VL(n+1));
dp[0][0] = 1;
replr(j, 1, n) dp[j][0] = dp[j-1][0]*b[j-1]%MOD;
replr(i, 1, n) replr(j, 1, n) {
dp[i][j] = dp[i-1][j-1]*a[i-1]%MOD + dp[i-1][j]*b[i-1]%MOD;
dp[i][j] %= MOD;
}
VL ret(n+1);
replr(i, 0, n) ret[i] = dp[n][i];
return ret;
}
void dfs1(int u = 0) {
for (int v : gp[u]) dfs1(v);
dpa[u] = dpb[u] = 0;
if (gp[u].size() == 0) {
if (val[u]) dpa[u] = 1;
else dpb[u] = 1;
return;
}
VL a, b;
for (int v : gp[u]) {
a.pb(dpa[v]);
b.pb(dpb[v]);
}
int c = gp[u].size();
VL s = subsets(a, b);
replr(i, 0, c) {
dpa[u] += s[i]*i % MOD;
dpa[u] %= MOD;
dpb[u] += s[i]*(c-i) % MOD;
dpb[u] %= MOD;
}
}
int count_ways(int L, int R) {
if (test6) {
seg.upd(L, R);
seg.print();
return seg.get();
/*cout << seg.get() << " == ";*/
/*return seg.get();*/
/*replr(i, L, R) val[i] = !val[i];*/
/*ll ans = 0;*/
/*rep(i, n) if (val[i]) ans += contr[i];*/
/*return ans;*/
}
replr(i, L, R) val[i] = !val[i];
dpa = dpb = VL(n);
dfs1();
return dpa[0];
}
Compilation message (stderr)
circuit.cpp: In constructor 'SEGTREE::SEGTREE(VI)':
circuit.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while (n < val.size()) n *= 2;
| ~~^~~~~~~~~~~~
# | 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... |