Submission #1185319

#TimeUsernameProblemLanguageResultExecution timeMemory
1185319anmattroiDigital Circuit (IOI22_circuit)C++17
2 / 100
6 ms1260 KiB
#include "circuit.h" #include <bits/stdc++.h> #define maxn 1005 #define fi first #define se second using namespace std; using ii = pair<int, int>; constexpr int mod = 1'000'002'022; inline constexpr void add(int &x, const int &y) {x += y; if (x >= mod) x -= mod;} int a[maxn], n, m; vector<int> adj[maxn]; int dp[maxn+maxn][2], f[maxn], c[maxn]; ii lis[maxn]; void pfs(int u) { if (u >= n) { c[u] = 0; return; } c[u] = 1; for (int v : adj[u]) { pfs(v); if (v < n) c[u] = 1LL * c[u] * c[v] % mod; } c[u] = 1LL * c[u] * int(adj[u].size()) % mod; } void init(int N, int M, vector<int> P, vector<int> A) { for (int i = 1; i < N+M; i++) adj[P[i]].emplace_back(i); for (int i = 0; i < M; i++) a[i+1] = A[i]; n = N; m = M; pfs(0); } void dfs(int u) { if (u >= n) { dp[u][a[u-n+1]] = 1; dp[u][1^a[u-n+1]] = 0; return; } int sz = 0; for (int v : adj[u]) { dfs(v); lis[++sz] = ii{dp[v][0], dp[v][1]}; } for (int i = 0; i <= sz; i++) f[i] = 0; f[0] = 1; for (int i = 1; i <= sz; i++) { for (int j = sz; j >= 1; j--) f[j] = (1LL * f[j] * lis[i].fi + 1LL * f[j-1] * lis[i].se) % mod; f[0] = 1LL * f[0] * lis[i].fi % mod; } int sum = 0; dp[u][0] = dp[u][1] = 0; for (int i = sz; i >= 1; i--) { add(sum, f[i]); add(dp[u][1], sum); } dp[u][0] = (c[u]-dp[u][1]+mod)%mod; } int count_ways(int L, int R) { for (int i = L-n+1; i <= R-n+1; i++) a[i] ^= 1; dfs(0); return dp[0][1]; } /* 3 4 3 -1 0 1 2 1 1 0 1 0 1 0 3 4 4 5 3 6 2 0 6 */
#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...