#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=2005;
const int MOD = 1e9 + 2022 ;
int a[nax];
long long dp[2][nax];
int n,m;
void merge(int pos){
dp[0][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[0][pos*2+1]*dp[0][pos*2+2]*2;
dp[1][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[1][pos*2+1]*dp[1][pos*2+2]*2;
dp[0][pos]%=MOD;
dp[1][pos]%=MOD;
}
void build(int pos,int l,int r){
if(l==r){
dp[a[l]][l]=1;
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
merge(pos);
}
void update(int pos,int l,int r,int idx){
if(l==r){
dp[a[l]][pos]=0;
a[l]^=1;
dp[a[l]][pos]=1;
return;
}
int mid=(r+l)/2;
if(idx<=mid) update(pos*2+1,l,mid,idx);
else update(pos*2+2,mid+1,r,idx);
merge(pos);
}
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) a[i]=A[i];
build(0,0,m-1);
}
int count_ways(int L, int R) {
L-=n;R-=n;
update(0,0,m-1,L);
return dp[1][0];
}
# | 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... |