#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000002022;
const int maxn=5000*2+5;
int n,m;
vector<int> v[maxn];
long long c[maxn],all=1;
long long mult(long long x,long long p)
{
if(p==1)return x;
long long h=mult(x,p/2);
if(p%2==0)return h*h%mod;
return h*h%mod*x%mod;
}
int a[maxn];
void dfs(int i)
{
c[i]=v[i].size();
if(v[i].size()==0)c[i]=1;
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
dfs(nb);
c[i]*=c[nb];
c[i]%=mod;
}
all*=c[i];
all%=mod;
//cout<<i<<" "<<c[i]<<endl;
}
long long b[200001];
long long c1[200001],c2[200001];
void dfs0(int i,int h)
{
if(v[i].size()==0)
{
//cout<<i<<" "<<h<<endl;
b[i]=h;
}
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
c1[nb]=c[nb];
if(j!=0)c1[nb]*=c1[v[i][j-1]];
c1[nb]%=mod;
}
for(int j=v[i].size()-1;j>=0;j--)
{
int nb=v[i][j];
c2[nb]=c[nb];
if(j!=v[i].size()-1)c2[nb]*=c2[v[i][j+1]];
c2[nb]%=mod;
}
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
long long curr=h;
if(j!=0)curr*=c1[v[i][j-1]];
curr%=mod;
if(j!=v[i].size()-1)curr*=c2[v[i][j+1]];
curr%=mod;
dfs0(nb,curr);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n=N;
m=M;
for(int i=1;i<P.size();i++)
v[P[i]].push_back(i);
for(int i=0;i<A.size();i++)
a[n+i]=A[i];
dfs(0);
dfs0(0,1);
return;
}
int count_ways(int L, int R)
{
for(int i=L;i<=R;i++)
{
a[i]^=1;
}
long long ans=0;
for(int i=n;i<=n+m-1;i++)
if(a[i])ans=(ans+b[i])%mod;
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |