Submission #1247457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247457		m5588ohammed	Digital Circuit (IOI22_circuit)	C++20	18 / 100	272 ms	13584 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define mod 1000002022
#define ll long long
ll n,m;
ll to[5001],tf[5001],cs[200001];
vector <ll> v[200001];
vector <vector<ll>> dp[5001];
ll calc(ll i,ll j,ll k){
	if(j==(int)v[i].size()){
		if(k==0) return dp[i][j][k]=1;
		else return dp[i][j][k]=0;
	}
	if(dp[i][j][k]!=-1) return dp[i][j][k];
	ll ans=0;
	if(k!=0) ans+=(calc(i,j+1,k-1)*to[v[i][j]])%mod;
	ans%=mod;
	ans+=(calc(i,j+1,k)*(tf[v[i][j]]-to[v[i][j]]+mod))%mod;
	ans%=mod;
	return dp[i][j][k]=ans;
}
void solve(ll i){
	to[i]=tf[i]=0;
	for(int j=0;j<v[i].size();j++){
		for(int k=0;k<=v[i].size();k++) dp[i][j][k]=-1;
	}
	if(n<=i){
		if(cs[i]==1) to[i]=1;
		else to[i]=0;
		tf[i]=1;
		//cout<<i<<" "<<to[i]<<" "<<tf[i]<<endl;
		return;
	}
	//cout<<"YUP"<<" "<<i<<" "<<v[i].size()<<endl;
	tf[i]=1;
	for(ll j:v[i]){
		solve(j);
		tf[i]=(tf[i]*tf[j])%mod;
	}
	tf[i]*=(int)v[i].size();
	tf[i]%=mod;
	for(ll k=1;k<=v[i].size();k++){
		calc(i,0,k);
		to[i]=(to[i]+dp[i][0][k]*k)%mod;
		//cout<<"HERE "<<i<<" "<<k<<" "<<dp[i][0][k]<<endl;
	}
	//cout<<i<<" "<<to[i]<<" "<<tf[i]<<endl;
	return;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n=N;m=M;
	for(int i=0;i<m;i++) cs[i+n]=A[i];
	for(int i=1;i<n+m;i++) v[P[i]].push_back(i);
	for(int i=0;i<n;i++){
		ll siz=v[i].size();
		dp[i].resize(siz+2,vector <ll> (siz+2));
	}
	//cout<<"HERE "<<cs[3]<<" "<<cs[4]<<endl;
	//cout<<"END BUILD"<<endl;
	return;
}

int count_ways(int L, int R){
	for(int i=L;i<=R;i++) {
		cs[i]^=1;
	}
	// for(int i=n;i<n+m;i++) cout<<cs[i]<<" ";
	// cout<<endl;
	solve(0);
	//cout<<"YES"<<endl;
	// cout<<"HERE "<<cs[6]<<" "<<cs[5]<<endl;
	//cout<<"END"<<endl;
	return to[0];
}
// 3 4 3
// -1 0 1 2 1 1 0
// 1 0 1 0
// 3 4
// 4 5
// 3 6


// 1 7 3
// -1 0 0 0 0 0 0 0
// 1 1 1 1 1 1 1
// 1 1
// 2 2
// 4 7

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