Submission #837172

#TimeUsernameProblemLanguageResultExecution timeMemory
837172tengiz05Digital Circuit (IOI22_circuit)C++17
18 / 100
3092 ms3096 KiB
#include "circuit.h" #include <vector> #include <array> #include <iostream> using namespace std; constexpr int P = 1E9 + 2022; int norm(int x) { if (x < 0) x += P; if (x >= P) x -= P; return x; } struct Z { int x; Z(int x = 0) : x(norm(x)) {} int val() { return x; } friend Z operator+(const Z &a, const Z &b) { return Z(a.x + b.x); } friend Z operator-(const Z &a, const Z &b) { return Z(a.x - b.x); } friend Z operator*(const Z &a, const Z &b) { return Z(int(a.x * 1LL * b.x % P)); } void operator += (const Z &o) { *this = *this + o; } }; int n, m; vector<int> a; vector<vector<int>> e; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N; m = M; e.resize(n); a = A; for (int i = 1; i < n + m; i++) { e[P[i]].push_back(i); } } int count_ways(int L, int R) { R++; L -= n; R -= n; for (int i = L; i < R; i++) { a[i] ^= 1; } // for (int i = 0; i < m; i++) cout << a[i]; // cout << "\n"; vector<array<Z, 2>> res(n + m); for (int i = 0; i < m; i++) { res[n + i][a[i]] = 1; } for (int i = n - 1; i >= 0; i--) { vector<Z> dp(e[i].size() + 1); dp[0] = 1; for (int j : e[i]) { vector<Z> ndp(e[i].size() + 1); for (int k = e[i].size(); k >= 0; k--) { if (k < int(e[i].size())) { ndp[k + 1] += dp[k] * res[j][1]; } ndp[k] += dp[k] * res[j][0]; } dp = ndp; } // cout << "node " << i << ": "; // for (int i = 0; i < int(dp.size()); i++) { // cout << dp[i].val() << " "; // } // cout << "\n"; int c = e[i].size(); res[i][0] += dp[0] * c; for (int j = 1; j < int(dp.size()); j++) { res[i][1] += dp[j] * j; res[i][0] += dp[j] * (c - j); } } return res[0][1].val(); }
#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...