This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
const int mod = 1000002022;
vector<int> state, p;
int n, m;
vector<vector<int>> g;
template<typename T>
int len(T &a){return a.size();}
vector<array<ll, 2>> dp;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M;
g.resize(n);
state = A;
p = P;
for(int i = 1; i < n + m; i ++){
g[p[i]].push_back(i);
}
dp.resize(n + m);
}
void dfs(int i){
if(i >= n){
dp[i][0] = state[i - n] ^ 1;
dp[i][1] = state[i - n];
return;
}
for(auto u : g[i]) dfs(u);
vector<ll> prep(len(g[i]) + 1);
prep[0] = 1;
ll al = len(g[i]);
int cur = 0;
for(auto u : g[i]){
cur ++;
al = al * (dp[u][0] + dp[u][1]) % mod;
for(int j = cur; j >= 0; j --){
prep[j] = prep[j] * dp[u][0] % mod;
if(j) prep[j] += prep[j - 1] * dp[u][1] % mod;
}
}
dp[i][1] = 0;
for(int j = 1; j <= len(g[i]); j ++){
//cout << prep[j] * j << endl;
dp[i][1] = (dp[i][1] + prep[j] * j) % mod;
}
dp[i][0] = al - dp[i][1];
if(dp[i][0] < 0) dp[i][0] += mod;
}
int count_ways(int l, int r) {
l -= n; r -= n;
for(int i = l; i <= r; i ++) state[i] ^= 1;
//for(int i = 0; i < m; i ++) cout << state[i] << ' ';
dfs(0);
return dp[0][1];
}
# | 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... |