#include "circuit.h"
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000002022;
vector<pair<ll, ll>>a;
vector<int>P;
vector<int>A;
vector<vector<int>>c;
int N, M;
vector<bool> F(200009, false);
vector<int> L, R;
void calc(int i)
{
int d = c[i].size();
vector<ll> k(d + 2, 0ll);
ll v = 1;
a[i] = {0ll, 0ll};
for (int j : c[i])
{
int v0 = a[j].first;
int v1 = a[j].second;
if (F[j])
swap(v0, v1);
ll a1_ = 0;
ll a0_ = 0;
a1_ = a[i].second * (v0 + v1) + v * v1;
a0_ = a[i].first * (v0 + v1) + v * v0;
a[i].first = a0_;
a[i].second = a1_;
v *= (v0 + v1);
a[i].first %= mod;
a[i].second %= mod;
v %= mod;
}
}
vector<ll>D;
void init(int N_, int M_, vector<int> P_, vector<int> A_) {
P = P_;
A = A_;
N = N_;
M = M_;
c = vector<vector<int>>(N + M);
for (int i = 1; i < N + M; i++)
c[P[i]].push_back(i);
ll prod[N + M];
{
function<void(int)>dfs = [&](int i)->void
{
prod[i] = max(1, (int)c[i].size());
for (int j : c[i])
{
dfs(j);
prod[i] *= prod[j];
prod[i] %= mod;
}
};
dfs(0);
}
D = vector<ll>(N + M);
{
function<void(int, ll)>dfs = [&](int i, ll ss)->void
{
D[i] = ss;
vector<ll>s;
int cnt = 0;
for (int j : c[i])
{
s.push_back(prod[j]);
cnt++;
}
vector<ll>t = s;
reverse(t.begin(), t.end());
s.insert(s.begin(), 1);
t.insert(t.begin(), 1);
for (int i = 1; i < (int)s.size(); i++)
s[i] = (s[i - 1] * s[i]) % mod;
for (int i = 1; i < (int)t.size(); i++)
t[i] = (t[i - 1] * t[i]) % mod;
int k = 0;
for (int j : c[i])
{
ll s_ = ss;
s_ *= s[k];
s_ %= mod;
s_ *= t[cnt - 1 - k];
s_ %= mod;
dfs(j, s_);
k++;
}
};
dfs(0, 1);
}
}
int count_ways(int X, int Y) {
X -= N;
Y -= N;
for (int i = X; i <= Y; i++)
A[i] ^= 1;
ll ret = 0;
for (int i = X; i <= Y; i++)
if (A[i] == 1)
{
ret += D[i + N];
ret %= mod;
}
return (int)ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
2nd lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
208 KB |
2nd lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
2nd lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
398 ms |
5044 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '37399904' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
398 ms |
5044 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '37399904' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
208 KB |
2nd lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
2nd lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
208 KB |
2nd lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |