Chromatic Polynomial (verify/math/chromatic_poly.test.cpp)

• View this file on GitHub
• Last update: 2025-12-26 19:46:08+01:00
• Problem: https://judge.yosupo.jp/problem/chromatic_polynomial

Depends on

• cp-algo/math/affine.hpp
• cp-algo/math/combinatorics.hpp
• cp-algo/math/common.hpp
• cp-algo/math/cvector.hpp
• cp-algo/math/fft.hpp
• cp-algo/math/poly.hpp
• cp-algo/math/poly/impl/div.hpp
• cp-algo/math/poly/impl/euclid.hpp
• cp-algo/math/subset_convolution.hpp
• cp-algo/number_theory/discrete_sqrt.hpp
• cp-algo/number_theory/modint.hpp
• cp-algo/random/rng.hpp
• cp-algo/util/big_alloc.hpp
• cp-algo/util/bit.hpp
• cp-algo/util/checkpoint.hpp
• cp-algo/util/complex.hpp
• cp-algo/util/simd.hpp

Code

// @brief Chromatic Polynomial
#define PROBLEM "https://judge.yosupo.jp/problem/chromatic_polynomial"
#pragma GCC optimize("O3,unroll-loops")
#include <bits/allocator.h>
#pragma GCC target("avx2")
#include <iostream>
#include "blazingio/blazingio.min.hpp"
#define CP_ALGO_CHECKPOINT
#include "cp-algo/number_theory/modint.hpp"
#include "cp-algo/math/subset_convolution.hpp"
#include "cp-algo/math/poly.hpp"
#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
using base = cp_algo::math::modint<mod>;
using polyn = cp_algo::math::poly_t<base>;

cp_algo::big_vector<base> indep_subsets(auto const& adj) {
    uint32_t n = (uint32_t)size(adj);
    uint32_t masks = 1 << n;
    cp_algo::big_vector<base> indep(masks);
    indep[0] = base(1);
    for(uint32_t v = 0; v < n; v++) {
        uint32_t delta = 1 << v;
        if (adj[v] & delta) continue;
        for(uint32_t mask = 0; mask < delta; mask++) {
            indep[mask + delta] = (adj[v] & mask) ? base(0) : indep[mask];
        }
    }
    return indep;
}

void solve() {
    size_t n, m;
    cin >> n >> m;
    vector<uint64_t> adj(n);
    for(size_t i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u] |= 1 << v;
        adj[v] |= 1 << u;
    }
    auto indep = indep_subsets(adj);
    cp_algo::big_vector<base> w(1 << n);
    w.back() = 1; // w[S] = 1 if S is the full set, else 0
    auto Y = cp_algo::math::subset_power_projection<base>(indep, w, n+1);
    cp_algo::big_vector<base> X(n+1);
    std::ranges::iota(X, 0);
    auto res = polyn::inter(X, Y);
    res.print((int)n+1);
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;// cin >> t;
    while(t--) {
        solve();
    }
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 327, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	big_00	AC	35 ms	11 MB
g++	big_01	AC	59 ms	13 MB
g++	big_02	AC	199 ms	29 MB
g++	big_03	AC	35 ms	11 MB
g++	big_04	AC	198 ms	30 MB
g++	big_05	AC	59 ms	13 MB
g++	big_06	AC	59 ms	13 MB
g++	big_07	AC	104 ms	17 MB
g++	big_08	AC	198 ms	30 MB
g++	big_09	AC	35 ms	11 MB
g++	clique_cycle_00	AC	199 ms	30 MB
g++	clique_cycle_01	AC	200 ms	30 MB
g++	clique_cycle_02	AC	198 ms	30 MB
g++	clique_cycle_03	AC	198 ms	29 MB
g++	example_00	AC	10 ms	10 MB
g++	example_01	AC	196 ms	29 MB
g++	example_02	AC	10 ms	10 MB
g++	example_03	AC	9 ms	10 MB
g++	loop_00	AC	10 ms	10 MB
g++	loop_01	AC	9 ms	10 MB
g++	multi_edge_00	AC	11 ms	10 MB
g++	multi_edge_01	AC	9 ms	10 MB
g++	multi_edge_02	AC	10 ms	10 MB
g++	multi_edge_03	AC	9 ms	10 MB
g++	random_00	AC	10 ms	10 MB
g++	random_01	AC	9 ms	10 MB
g++	random_02	AC	11 ms	10 MB
g++	random_03	AC	10 ms	10 MB
g++	random_04	AC	200 ms	30 MB
g++	random_05	AC	11 ms	10 MB
g++	random_06	AC	10 ms	10 MB
g++	random_07	AC	104 ms	16 MB
g++	random_08	AC	17 ms	10 MB
g++	random_09	AC	9 ms	10 MB

Back to top page