// AM + DG
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
// I was stuck in the paradigm that I can't divide
// But, I can! It's just a matter of whether or not I can deal with a nonprime modulus
const ll MODS[4] = {2ll, 223ll, 2'242'157ll, 1'000'002'022ll};
// Fast Modular Exponentiation
ll fpw(ll base, ll pw, ll md) {
base = base % md;
if(pw == 0ll) return 1ll;
ll bsqr = fpw(base * base, pw >> 1ll, md);
return (pw & 0b1ll ? (base * bsqr) % md : bsqr);
}
// Modular Multiplicative inverse
// ! CAREFUL, only works for prime modulus
ll inv(ll base, ll md) {
return fpw(base, md - 2ll, md);
}
// This doesn't need to be as complicated as
// your code for pre-in-post
// Only multiplication and division are required
class ModInt {
public:
ll m; // Mantissa, guaranteed to be nonzero
ll pw;
ll md;
ModInt(ll n, ll a_md): md(a_md) {
ll cpw = 0ll;
while((n % md) == 0ll) {
n /= md;
cpw++;
}
m = n;
pw = cpw;
}
ModInt(ll a_m, ll a_pw, ll a_md): m(a_m), pw(a_pw), md(a_md) {
assert(m != 0ll);
assert(a_pw >= 0ll);
}
ModInt operator*(const ModInt& o) const {
return {(m * o.m) % md, pw + o.pw, md};
}
ModInt operator/(const ModInt& o) const {
return {(m * inv(o.m, md)) % md, pw - o.pw, md};
}
// Returns this number mod the modulus
ll to_num() const {
return (pw == 0ll ? m % md : 0ll);
}
};
class CRTInt {
public:
ModInt m1, m2, m3;
CRTInt(ll n): m1(n, MODS[0ll]), m2(n, MODS[1ll]), m3(n, MODS[2ll]) {};
CRTInt(ModInt a_m1, ModInt a_m2, ModInt a_m3): m1(a_m1), m2(a_m2), m3(a_m3) {}
CRTInt operator*(const CRTInt& o) const {
return {m1 * o.m1, m2 * o.m2, m3 * o.m3};
}
CRTInt operator/(const CRTInt& o) const {
return {m1 / o.m1, m2 / o.m2, m3 / o.m3};
}
ll to_num() const {
ll res = 0ll;
ll f1 = fpw(MODS[1ll] * MODS[2ll], MODS[0ll] - 1ll, MODS[3ll]);
res += m1.to_num() * f1;
res %= MODS[3ll];
ll f2 = fpw(MODS[0ll] * MODS[2ll], MODS[1ll] - 1ll, MODS[3ll]);
res += m2.to_num() * f2;
res %= MODS[3ll];
ll f3 = fpw(MODS[0ll] * MODS[1ll], MODS[2ll] - 1ll, MODS[3ll]);
res += m3.to_num() * f3;
res %= MODS[3ll];
return res;
}
};
typedef vector<CRTInt> vci;
vvll adj;
vll a_ll;
ll n, m;
vci num_tot;
vb num_tot_vis;
CRTInt count_tot(ll i, const vvll& adj) {
CRTInt& ans = num_tot[i];
if(!num_tot_vis[i]) {
ll nc = adj[i].size();
ans = CRTInt(max(nc, 1ll));
if(nc > 0ll) {
for(ll j : adj[i]) {
ans = ans * count_tot(j, adj);
}
}
num_tot_vis[i] = true;
}
return ans;
}
vci root_path_prod;
void compute_root_path_prod(ll i, CRTInt cur_prod, const vvll& adj) {
root_path_prod[i] = cur_prod;
for(ll j : adj[i]) {
compute_root_path_prod(j, cur_prod * num_tot[j], adj);
}
}
class Tree {
public:
Tree *lt, *rt;
ll l, r;
ll v;
ll nv;
bool marked;
Tree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(0ll), nv(0ll), marked(false) {};
void push() {
if(!marked) return;
marked = false;
if(lt == nullptr) return;
lt->half_push();
rt->half_push();
}
void half_push() {
marked = !marked;
swap(v, nv);
}
void pull() {
v = (lt->v + rt->v) % MODS[3ll];
nv = (lt->nv + rt->nv) % MODS[3ll];
}
void build(const vll& a, const vll& contribs) {
if(l == r) {
(a[l] == 1ll ? v : nv) = contribs[l];
return;
}
ll m = (l + r) >> 1ll;
lt = new Tree(l, m);
rt = new Tree(m + 1ll, r);
lt->build(a, contribs);
rt->build(a, contribs);
pull();
}
ll qry(ll ql, ll qr) {
if(ql > r || qr < l) return 0ll;
push();
if(ql == l && qr == r) return v;
ll m = (l + r) >> 1ll;
return (lt->qry(ql, min(m, qr)) + rt->qry(max(m + 1ll, ql), qr)) % MODS[3ll];
}
void upd(ll ql, ll qr) {
if(ql > r || qr < l) return;
push();
if(ql == l && qr == r) {
half_push();
return;
}
ll m = (l + r) >> 1ll;
lt->upd(ql, min(m, qr));
rt->upd(max(m + 1ll, ql), qr);
pull();
}
};
Tree* tr;
void init(int N, int M, vi P, vi A) {
n = N; m = M;
L(i, 0ll, N + M) {
vll adjr;
adj.pb(adjr);
}
L(i, 1ll, N + M) {
adj[P[i]].pb(i);
}
num_tot.reserve(N + M);
num_tot_vis.reserve(N + M);
root_path_prod.reserve(N + M);
L(i, 0ll, N + M) {
num_tot.pb({1ll});
num_tot_vis.pb(false);
root_path_prod.pb({1ll});
}
a_ll.reserve(M);
for(int v : A) a_ll.pb((ll)v);
count_tot(0ll, adj);
compute_root_path_prod(0ll, CRTInt(1ll), adj);
vll contribs(m, 0ll);
CRTInt prod_of_ways(1ll);
// ! Starts at 1 because the root is not included
L(i, 1ll, n + m) {
prod_of_ways = prod_of_ways * num_tot[i];
}
// Compute the contributions to the sum! :))
L(i, 0ll, m) {
contribs[i] = (prod_of_ways / root_path_prod[i + n]).to_num();
}
// Build the segtree
tr = new Tree(0, m - 1ll);
tr->build(a_ll, contribs);
}
int count_ways(int L, int R) {
L -= n;
R -= n;
assert(0 <= L && L < m);
assert(0 <= R && R < m);
tr->upd(L, R);
return tr->qry(0ll, m - 1ll);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '422300014' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '422300014' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
484 ms |
17600 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '802124954' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
484 ms |
17600 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '802124954' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '422300014' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '422300014' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '422300014' |
| 11 |
Halted |
0 ms |
0 KB |
- |
