제출 #1058086

#제출 시각아이디문제언어결과실행 시간메모리
1058086dozer디지털 회로 (IOI22_circuit)C++17
18 / 100
3078 ms31952 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define sp " " #define endl "\n" #define pii pair<int, int> #define st first #define nd second #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define pb push_back #define LL node * 2 #define RR node * 2 + 1 #define ll long long #define MAXN 500005 const int modulo = 1000002022; const ll INF = 2e18 + 7; int add(ll a, ll b){ if (a + b < modulo) return a + b; return a + b - modulo; } int subs(ll a, ll b){ if (a < b) return a - b + modulo; return a - b; } int mul(ll a, ll b){ return (a * b) % modulo; } int fe(ll a, ll b){ if (b == 0) return 1; if (b % 2) return mul(a, fe(a, b - 1)); int tmp = fe(a, b / 2); return mul(tmp, tmp); } vector<int> adj[MAXN]; vector<int> dp[MAXN]; int one[MAXN], zero[MAXN], arr[MAXN]; int n, m; void dfs(int node){ if (adj[node].empty()){ if (arr[node - n]) one[node] = 1; else one[node] = 0; zero[node] = 1 - one[node]; return; } int k = adj[node].size(); dp[node].resize(k + 1, 0); fill(dp[node].begin(), dp[node].end(), 0); dp[node][0] = 1; for (auto i : adj[node]){ dfs(i); for (int j = k; j >= 1; j--){ dp[node][j] = add(mul(dp[node][j], zero[i]), mul(dp[node][j - 1], one[i])); } dp[node][0] = mul(dp[node][0], zero[i]); } zero[node] = 0, one[node] = 0; for (int i = 0; i <= k; i++){ zero[node] = add(zero[node], mul(dp[node][i], k - i)); one[node] = add(one[node], mul(dp[node][i], i)); } } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N, m = M; for (int i = 1; i < n + m; i++) adj[P[i]].pb(i); for (int i = 0; i < m; i++) arr[i] = A[i]; } int count_ways(int L, int R) { for (int i = L - n; i <= R - n; i++) arr[i] ^= 1; dfs(0); return one[0]; } /* int main() { fileio(); int N, M, Q; assert(3 == scanf("%d %d %d", &N, &M, &Q)); std::vector<int> P(N + M), A(M); for (int i = 0; i < N + M; ++i) { assert(1 == scanf("%d", &P[i])); } for (int j = 0; j < M; ++j) { assert(1 == scanf("%d", &A[j])); } init(N, M, P, A); for (int i = 0; i < Q; ++i) { int L, R; assert(2 == scanf("%d %d", &L, &R)); printf("%d\n", count_ways(L, R)); } return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...