제출 #1128939

#제출 시각아이디문제언어결과실행 시간메모리
1128939vladilius디지털 회로 (IOI22_circuit)C++20
18 / 100
3058 ms7452 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second const int mod = 1000002022; vector<vector<int>> g, dp; vector<int> a; int n, m; void fill(int v){ if (g[v].empty()) return; int k = (int) g[v].size(), pr = k; for (int i: g[v]){ fill(i); pr = (1LL * pr * (dp[i][0] + dp[i][1])) % mod; } vector<vector<int>> f(k + 1, vector<int>(k + 1)); f[0][0] = 1; for (int i = 1; i <= k; i++){ int u = g[v][i - 1]; f[i][0] = (1LL * f[i - 1][0] * dp[u][0]) % mod; for (int j = 1; j <= k; j++){ f[i][j] = (1LL * f[i - 1][j] * dp[u][0] + 1LL * f[i - 1][j - 1] * dp[u][1]) % mod; } } dp[v][1] = 0; for (int i = 1; i <= k; i++){ dp[v][1] = (dp[v][1] + 1LL * i * f[k][i]) % mod; } dp[v][0] = (pr - dp[v][1]) % mod; if (dp[v][0] < 0) dp[v][0] += mod; } int count_ways(int l, int r){ l -= n; r -= n; for (int i = l; i <= r; i++){ a[i] = !a[i]; } for (int i = n; i < n + m; i++){ dp[i][1] = a[i - n]; dp[i][0] = !dp[i][1]; } fill(0); return dp[0][1]; } void init(int N, int M, vector<int> p, vector<int> A){ n = N; m = M; a = A; g.resize(n + m); for (int i = 1; i < n + m; i++){ g[p[i]].pb(i); } dp.resize(n + m); for (int i = 0; i < dp.size(); i++){ dp[i].resize(2); } }
#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...