Submission #837394

#	Time	Username	Problem	Language	Result	Execution time	Memory
837394		NothingXD	Digital Circuit (IOI22_circuit)	C++17	100 / 100	886 ms	23880 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

const int mod = 1000002022;

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define add(x, y) (x + y >= mod? x+y-mod: x+y)
#define sub(x, y) (x - y < 0? x-y+mod: x-y)

const int maxn = 1e5 + 10;

int n, m, p[maxn << 1], a[maxn], dp[maxn], val[maxn], cnt[maxn][2], phi = 1 * 222 * 2242156;
pii seg[maxn << 2];
bool lazy[maxn << 2];
vector<int> g[maxn];

int pw(int a, int b){
//	debug(a, b);
	int res = 1;
	for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
//	debug(res);
	return res;
}

pair<int,pii> dfs(int v){
	if (v >= n){
		val[v] = 1;
		return {1, {0, 0}};
	}
	int x = g[v].size();
	while(x % 2 == 0){
		cnt[v][0]++;
		x /= 2;
	}
	while(x % 223 == 0){
		cnt[v][1]++;
		x /= 223;
	}
	val[v] = x;
	pair<int,pii> res = {val[v], {cnt[v][0], cnt[v][1]}};
	for (auto u: g[v]){
		pair<int,pii> tmp = dfs(u);
		res.F = 1ll * res.F * tmp.F % mod;
		res.S.F += tmp.S.F;
		res.S.S += tmp.S.S;
	}
	return res;
}

void solve(int v, pair<int,pii> tmp){
	//debug(v);
	if (v >= n){
		dp[v-n] = 1ll * tmp.F * pw(2, tmp.S.F) % mod * pw(223, tmp.S.S) % mod;
	//	debug(v, dp[v-n], tmp.F, tmp.S.F, tmp.S.S);
		return;
	}
	tmp.F = 1ll * tmp.F * pw(val[v], phi-1) % mod;
	tmp.S.F -= cnt[v][0];
	tmp.S.S -= cnt[v][1];
	for (auto u: g[v]){
		solve(u, tmp);
	}
}

pii operator +(pii a, pii b){
	return MP(add(a.F, b.F), add(a.S, b.S));
}

void shift(int v, int l, int r);

void build(int v, int l, int r){
	if (l + 1 == r){
		seg[v] = {dp[l], 0};
		if (a[l] == 0) swap(seg[v].F, seg[v].S);
		return;
	}
	int mid = (l + r) >> 1;
	build(v << 1, l, mid);
	build(v << 1 | 1, mid, r);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void change(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		swap(seg[v].F, seg[v].S);
		lazy[v] = !lazy[v];
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, ql, qr);
	change(v << 1 | 1, mid, r, ql, qr);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void shift(int v, int l, int r){
	if (!lazy[v]) return;
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, l, mid);
	change(v << 1 | 1, mid, r, mid, r);
	lazy[v] = false;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n = N;
	m = M;
	for (int i = 1; i < n+m; i++){
		p[i] = P[i];
		g[p[i]].push_back(i);
	}
	for (int i = 0; i < m; i++) a[i] = A[i];
//	debug(1);
	pair<int,pii> tmp = dfs(0);
//	debug(tmp.F, tmp.S.F, tmp.S.S);
//	debug(2);
	solve(0, tmp);
//	debug(3);
	build(1, 0, m);
}

int count_ways(int L, int R) {
	L -= n;
	R -= n;
	change(1, 0, m, L, R+1);
	return seg[1].F;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11