Submission #975033

#	Time	Username	Problem	Language	Result	Execution time	Memory
975033		PenguinsAreCute	Digital Circuit (IOI22_circuit)	C++17	100 / 100	726 ms	9040 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 2022;
const int TOT = 497758632;
const int MAXN = 121010;
// https://codeforces.com/blog/entry/18051
bool lazy[MAXN]; int val[MAXN<<1], sum[MAXN<<1];
int h = sizeof(int) * 8 - __builtin_clz(MAXN);
void app(int x) {
	val[x] = sum[x] - val[x];
	if(val[x]<0) val[x]+=MOD;
	if(x<MAXN) lazy[x]^=1;
}
void build(int x) {
	while(x>>=1) {
		int erm = val[x<<1]+val[x<<1|1];
		if(erm>=MOD) erm-=MOD;
		val[x]=(lazy[x]?(sum[x]<erm?sum[x]-erm+MOD:sum[x]-erm):erm);
	}
}
void push(int x) {
	for(int s=h;s;--s) {
		int i = x>>s;
		if(lazy[i]) app(i<<1),app(i<<1|1);
		lazy[i]=0;
	}
}
void up(int l, int r) {
	l += MAXN, r += MAXN;
	int l0 = l, r0 = r;
	for(;l<r;l>>=1,r>>=1) {
		if(l&1) app(l++);
		if(r&1) app(--r);
	}
	build(l0); build(r0-1);
}
int qry(int l, int r) {
	l += MAXN, r+=MAXN;
	push(l); push(r-1);
	int ans = 0;
	for(;l<r;l>>=1,r>>=1) {
		if(l&1) {ans+=val[l++]; if(ans>=MOD) ans-=MOD;}
		if(r&1) {ans+=val[--r]; if(ans>=MOD) ans-=MOD;}
	}
	return ans;
}
int exp(int a, int b) {
	if(!b) return 1;
	return (1LL*exp((1LL*a*a)%MOD,b>>1)*(b&1?a:1))%MOD;
}
int n, m;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n = N;
	m = M;
	int deg[N+M], deg2[N+M], deg223[N+M], weight[N+M], weight2[N+M], weight223[N+M];
	fill(deg,deg+N+M,0);
	fill(deg2,deg2+N+M,0);
	fill(deg223,deg223+N+M,0);
	for(int i=1;i<N+M;i++) deg[P[i]]++;
	for(int i=0;i<N;i++) {
		while(!(deg[i]%2)) deg[i]/=2, deg2[i]++;
		while(!(deg[i]%223)) deg[i]/=223, deg223[i]++;
	}
	int ways = 1, ways2 = 0, ways223 = 0;
	for(int i=0;i<N;i++) ways = (1LL * ways * deg[i]) % MOD, ways2+=deg2[i], ways223+=deg223[i];
	weight[0]=1; weight2[0] = weight223[0] = 0;
	for(int i=1;i<N+M;i++) weight[i] = (1LL*weight[P[i]] * exp(deg[P[i]], TOT - 1))%MOD, weight2[i] = weight2[P[i]] - deg2[P[i]], weight223[i] = weight223[P[i]] - deg223[P[i]];
	for(int i=0;i<M;i++) {
		sum[i+MAXN] = (1LL * weight[i+N] * ways) % MOD;
		sum[i+MAXN] = (1LL * sum[i+MAXN] * exp(2,ways2 + weight2[i+N])) % MOD;
		sum[i+MAXN] = (1LL * sum[i+MAXN] * exp(223,ways223 + weight223[i+N])) % MOD;
		val[i+MAXN] = sum[i+MAXN]*A[i];
	}
	for(int i=MAXN;--i;) {
		sum[i]=sum[i<<1]+sum[i<<1|1];
		if(sum[i]>=MOD) sum[i]-=MOD;
		val[i]=val[i<<1]+val[i<<1|1];
		if(val[i]>=MOD) val[i]-=MOD;
	}
}
int count_ways(int L, int R) {
	up(L-n,R-n+1);
	return qry(0,m);
}
/*
main() {
	int x = 1e9 + 2022; ll totient = 1e9 + 2022;
	for(int i=2;x>1;i++) if(!(x%i)) {
		while(!(x%i)) x /= i;
		totient *= (i-1); totient /= i;
		cout << i << " ";
	}
	cout << totient;
}
*/

• 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