Submission #1247449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247449		m5588ohammed	Digital Circuit (IOI22_circuit)	C++20	0 / 100	10 ms	8164 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;
	//cout<<i<<" "<<j<<" "<<k<<" "<<v[i][j]<<" "<<to[v[i][j]]<<" "<<ans<<endl;
	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;
	}
	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<<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+1,vector <ll> (siz+1));
	}
	//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;
	solve(0);
	// 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

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