sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_cliques" #include "../../math/modint.hpp" #include "../../graph/enumerate_cliques.hpp" #include <bits/stdc++.h> using namespace std; using mint = Modint<998244353>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<mint> x(N); for (auto& y : x) cin >> y; vector<vector<bool>> G(N, vector<bool>(N)); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u][v] = G[v][u] = true; } mint ans = 0; for (auto& clique : enumerate_cliques(G)) { mint res = 1; for (int i : clique) { res *= x[i]; } ans += res; } cout << ans << endl; }
#line 1 "test/yosupo/enumerate_cliques.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/enumerate_cliques" #line 2 "math/modint.hpp" #include <algorithm> #include <iostream> /** * @brief Mod int */ template <int m> class Modint { using mint = Modint; static_assert(m > 0, "Modulus must be positive"); public: static constexpr int mod() { return m; } constexpr Modint(long long y = 0) : x(y >= 0 ? y % m : (y % m + m) % m) {} constexpr int val() const { return x; } constexpr mint& operator+=(const mint& r) { if ((x += r.x) >= m) x -= m; return *this; } constexpr mint& operator-=(const mint& r) { if ((x += m - r.x) >= m) x -= m; return *this; } constexpr mint& operator*=(const mint& r) { x = static_cast<int>(1LL * x * r.x % m); return *this; } constexpr mint& operator/=(const mint& r) { return *this *= r.inv(); } constexpr bool operator==(const mint& r) const { return x == r.x; } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint(-x); } constexpr friend mint operator+(const mint& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(const mint& l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(const mint& l, const mint& r) { return mint(l) *= r; } constexpr friend mint operator/(const mint& l, const mint& r) { return mint(l) /= r; } constexpr mint inv() const { int a = x, b = m, u = 1, v = 0; while (b > 0) { int t = a / b; std::swap(a -= t * b, b); std::swap(u -= t * v, v); } return mint(u); } constexpr mint pow(long long n) const { mint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend std::ostream& operator<<(std::ostream& os, const mint& r) { return os << r.x; } friend std::istream& operator>>(std::istream& is, mint& r) { long long t; is >> t; r = mint(t); return is; } private: int x; }; #line 2 "graph/enumerate_cliques.hpp" #include <cmath> #include <vector> std::vector<std::vector<int>> enumerate_cliques( const std::vector<std::vector<bool>>& G) { int N = G.size(), M = 0; std::vector<int> deg(N); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (G[i][j]) { ++deg[i]; ++M; } } } M /= 2; int B = std::sqrt(2 * M); std::vector<std::vector<int>> cliques; auto check = [&](const std::vector<int>& vs, bool use_first) { int n = vs.size(); for (int S = 1; S < 1 << n; ++S) { if (use_first && !(S & 1)) continue; bool ok = true; for (int i = 0; i < n - 1; ++i) { if (!(S >> i & 1)) continue; for (int j = i + 1; j < n; ++j) { if ((S >> j & 1) && !G[vs[i]][vs[j]]) { ok = false; break; } } if (!ok) break; } if (ok) { cliques.emplace_back(); for (int i = 0; i < n; ++i) { if (S >> i & 1) { cliques.back().push_back(vs[i]); } } } } }; std::vector<bool> checked(N); std::vector<int> big; for (int i = 0; i < N; ++i) { if (deg[i] >= B) { big.push_back(i); continue; } std::vector<int> vs; vs.push_back(i); for (int j = 0; j < N; ++j) { if (G[i][j] && !checked[j]) { vs.push_back(j); } } check(vs, true); checked[i] = true; } check(big, false); return cliques; } #line 5 "test/yosupo/enumerate_cliques.test.cpp" #include <bits/stdc++.h> using namespace std; using mint = Modint<998244353>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<mint> x(N); for (auto& y : x) cin >> y; vector<vector<bool>> G(N, vector<bool>(N)); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u][v] = G[v][u] = true; } mint ans = 0; for (auto& clique : enumerate_cliques(G)) { mint res = 1; for (int i : clique) { res *= x[i]; } ans += res; } cout << ans << endl; }