src/graph/cnt/chrom_num/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../bit/parity/lib.hpp" | ||
| 4 | #include "../../../math/mul_mod/lib.hpp" | ||
| 5 | #include "../../../util/alias/others/lib.hpp" | ||
| 6 | #include "../../ds/graph_c/lib.hpp" | ||
| 7 | |||
| 8 | namespace tifa_libs { | ||
| 9 | namespace chrom_num_impl_ { | ||
| 10 | template <u32 mod> | ||
| 11 | 52 | CEXP u32 calc(u32 n, vecpti hist) NE { | |
| 12 |
2/4unsigned int tifa_libs::chrom_num_impl_::calc<1000000021u>(unsigned int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >):
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
unsigned int tifa_libs::chrom_num_impl_::calc<1000000033u>(unsigned int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >):
✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
|
288 | flt_ (u32, c, 1, n + 1) { |
| 13 | 288 | i64 _ = 0; | |
| 14 |
4/4unsigned int tifa_libs::chrom_num_impl_::calc<1000000021u>(unsigned int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >):
✓ Branch 8 taken 37292 times.
✓ Branch 9 taken 144 times.
unsigned int tifa_libs::chrom_num_impl_::calc<1000000033u>(unsigned int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >):
✓ Branch 8 taken 37292 times.
✓ Branch 9 taken 144 times.
|
74872 | for (auto& [i, x] : hist) _ += (x = (i32)mul_mod_s(x, i, mod)); |
| 15 |
4/4unsigned int tifa_libs::chrom_num_impl_::calc<1000000021u>(unsigned int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >):
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 118 times.
unsigned int tifa_libs::chrom_num_impl_::calc<1000000033u>(unsigned int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >):
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 118 times.
|
288 | if (_ % (i32)mod) return c; |
| 16 | } | ||
| 17 | ✗ | return n; | |
| 18 | } | ||
| 19 | } // namespace chrom_num_impl_ | ||
| 20 | |||
| 21 | 26 | CEXP u32 chrom_num(graph_c auto CR g) NE { | |
| 22 | 26 | cu32 n = g.vsize(); | |
| 23 | 78 | vecu adj(n), dp(1 << n); | |
| 24 |
2/2✓ Branch 0 taken 389 times.
✓ Branch 1 taken 26 times.
|
415 | flt_ (u32, i, 0, n) |
| 25 |
2/2✓ Branch 10 taken 3076 times.
✓ Branch 11 taken 389 times.
|
3465 | for (auto to : g[i]) adj[i] |= 1 << (u32)to, adj[(u32)to] |= 1 << i; |
| 26 | 26 | dp[0] = 1; | |
| 27 |
2/2✓ Branch 0 taken 11703434 times.
✓ Branch 1 taken 26 times.
|
11703460 | flt_ (u32, i, 1, 1u << n) { |
| 28 | 11703434 | cu32 k = i & (i - 1); | |
| 29 | 11703434 | dp[i] = dp[k] + dp[k & ~adj[(u32)std::countr_zero(i)]]; | |
| 30 | } | ||
| 31 | 26 | veci _((1 << n) + 1); | |
| 32 |
4/4✓ Branch 1 taken 5851730 times.
✓ Branch 2 taken 5851730 times.
✓ Branch 5 taken 11703460 times.
✓ Branch 6 taken 26 times.
|
11703486 | flt_ (u32, i, 0, 1u << n) _[dp[i]] += parity(i) ? -1 : 1; |
| 33 | 26 | vecpti hist; | |
| 34 |
2/2✓ Branch 0 taken 11703460 times.
✓ Branch 1 taken 26 times.
|
11703486 | flt_ (u32, i, 1, (1u << n) + 1) |
| 35 |
2/2✓ Branch 1 taken 8971 times.
✓ Branch 2 taken 11694489 times.
|
11703460 | if (_[i]) hist.emplace_back(i, _[i]); |
| 36 | 26 | return min(chrom_num_impl_::calc<1000000021>(n, hist), chrom_num_impl_::calc<1000000033>(n, hist)); | |
| 37 | 26 | } | |
| 38 | |||
| 39 | } // namespace tifa_libs | ||
| 40 |