| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1077479 | Faisal_Saqib | 디지털 회로 (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll NP=2e5+100,mod=1e9+2022;
ll n,m,p[NP],a[NP];
vector<ll> ma[NP];
ll dp[NP][2],lazy[NP],dp1[NP][2];
void compute(int x=0,bool continue_=1)
{
dp[x][0]=dp[x][1]=0;
dp1[x][0]=dp1[x][1]=0;
if(n<=x){
dp[x][a[x-n]]=1;
dp1[x][1-a[x-n]]=1;
return;
}
int sz=ma[x].size();
vector<int> tmp(sz+1);
// DP 1
tmp[0]=1;
for(auto y:ma[x])
{
if(continue_)
compute(y);
for(int j=sz;j>=0;j--)
{
if(j==0)
{
tmp[j]=(tmp[j]*dp[y][0])%mod;
}
else
{
tmp[j]=(tmp[j]*dp[y][0])%mod;
tmp[j]=(tmp[j] + ((tmp[j-1]*dp[y][1])%mod))%mod;
}
}
}
int sm=0;
for(int j=sz;j>=1;j--)
{
sm = ( sm + tmp[j] ) % mod;
dp[x][1] = ( dp[x][1] + sm ) % mod;
}
sm=tmp[0];
for(int j=1;j<=sz;j++)
{
dp[x][0] = ( dp[x][0] + sm ) % mod;
sm = ( sm + tmp[j] ) % mod;
}
// Dp 1
for(int j=0;j<=sz;j++)tmp[j]=0;
tmp[0]=1;
for(auto y:ma[x])
{
for(int j=sz;j>=0;j--)
{
if(j==0)
{
tmp[j]=(tmp[j]*dp1[y][0])%mod;
}
else
{
tmp[j]=(tmp[j]*dp1[y][0])%mod;
tmp[j]=(tmp[j] + ((tmp[j-1]*dp1[y][1])%mod))%mod;
}
}
}
sm=0;
for(int j=sz;j>=1;j--)
{
sm = ( sm + tmp[j] ) % mod;
dp1[x][1] = ( dp1[x][1] + sm ) % mod;
}
sm=tmp[0];
for(int j=1;j<=sz;j++)
{
dp1[x][0] = ( dp1[x][0] + sm ) % mod;
sm = ( sm + tmp[j] ) % mod;
}
}
void prepro(int x=0){
if(n<=x)
{
lc[x]=rc[x]=-1;
return;
}
lc[x]=ma[x][0];
rc[x]=ma[x][1];
prepro(lc[x]);
prepro(rc[x]);
}
void push(int v)
{
lazy[lc[v]]^=lazy[v];
lazy[rc[v]]^=lazy[v];
if(lazy[v])
{
swap(dp[v][0],dp1[v][0]);
swap(dp[v][1],dp1[v][1]);
}
}
void update(int v,int l,int r,int ql,int qr)
{
if(qr<l or r<ql) // nothing changes here
return;
if(ql<=l and r<=qr) // whole subtree to be updated
{
lazy[v]^=1;
return;
}
push(v);
int mid=(l+r)/2;
update(lc[v],l,mid,ql,qr);
update(rc[v],mid+1,r,ql,qr);
compute(v,0);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n=N,m=M;
for(ll i=0;i<n+m;i++)
{
p[i]=P[i];
if(p[i]!=-1)ma[p[i]].push_back(i);
}
for(ll j=0;j<m;j++)a[j]=A[j];
prepro();
compute();
}
int count_ways(int L, int R)
{
for(ll i=L-n;i<=R-n;i++)a[i]=(a[i]?0:1);
update(0,0,m-1,L-n,R-n);
push(0);
return (int)dp[0][1];
}