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 <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#else
#define D(x) ;
#endif
using namespace std;
using ll = long long;
int n, m;
vector<int> ps;
vector<int> as;
vector<vector<int>> al;
vector<int> tss;
vector<int> tcs;
vector<int> td1;
vector<int> td2;
vector<int> ts1;
vector<int> ts2;
vector<int> mults;
constexpr int m2 = 2242157;
constexpr int mod = 2*223*m2;
constexpr int ord = 222*2242156;
int bexp(ll b, ll e) {
if(e < 0) e += ord;
ll r = 1;
while(e > 0) {
if(e&1) {
r *= b;
r %= mod;
}
e /= 2;
b *= b;
b %= mod;
}
return r;
}
void iwalk(int v) {
tcs[v] = 1;
tss[v] = 1;
int c = al[v].size()-1;
if(ps[v] == -1) c += 1;
if(c == 0) return;
while(c % 2 == 0) {
c /= 2;
ts1[v] += 1;
}
while(c % 223 == 0) {
c /= 223;
ts2[v] += 1;
}
tss[v] = c;
D(v)
D(tss[v])
for(auto a : al[v]) {
if(a == ps[v]) continue;
iwalk(a);
tcs[v] *= tss[a];
tcs[v] %= mod;
td1[v] += ts1[a];
td2[v] += ts2[a];
}
tss[v] *= tcs[v];
tss[v] %= mod;
ts1[v] += td1[v];
ts2[v] += td2[v];
}
void mwalk(int v, int ml, int d1, int d2) {
if(v >= n) {
mults[v-n] = ml;
mults[v-n] = (1ll*bexp(2, d1)*mults[v-n]) % mod;
mults[v-n] = (1ll*bexp(223, d2)*mults[v-n]) % mod;
}
for(auto a : al[v]) {
if(a == ps[v]) continue;
ll nm = 1ll*ml*tcs[v];
nm %= mod;
nm *= bexp(tss[a], -1);
nm %= mod;
mwalk(a, nm, d1+td1[v]-ts1[a], d2+td2[v]-ts2[a]);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
ps = std::move(P);
as = std::move(A);
al.resize(N+M);
mults.resize(M);
tcs.resize(N+M);
td1.resize(N+M);
td2.resize(N+M);
tss.resize(N+M);
ts1.resize(N+M);
ts2.resize(N+M);
for(int i = 1; i < n+m; ++i) {
al[i].push_back(ps[i]);
al[ps[i]].push_back(i);
}
iwalk(0);
mwalk(0, 1, 0, 0);
if(0) {
for(int i = 0; i < n+m; ++i) {
cerr << tcs[i] << ' ';
}
cerr << '\n';
for(int i = 0; i < m; ++i) {
cerr << mults[i] << ' ';
}
cerr << '\n';
}
}
int count_ways(int L, int R) {
L -= n;
R -= n;
++R;
int res = 0;
for(int i = L; i < R; ++i) {
as[i] = 1 - as[i];
}
for(int i = 0; i < m; ++i) {
res += as[i] * mults[i];
res %= mod;
}
return res;
}
# | 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... |