test/cpv/library-checker-graph/counting_eulerian_circuits.mints-ms64.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #define AUTO_GENERATED | ||
| 2 | // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/counting_eulerian_circuits/ | ||
| 3 | #include "../../../src/comb/seq/fact/lib.hpp" | ||
| 4 | #include "../../../src/graph/ds/alist/lib.hpp" | ||
| 5 | #include "../../../src/graph/ds/amat/lib.hpp" | ||
| 6 | #include "../../../src/graph/ds/info/lib.hpp" | ||
| 7 | #include "../../../src/graph/euler_trail/lib.hpp" | ||
| 8 | #include "../../../src/graph/kirchhoff/lib.hpp" | ||
| 9 | #include "../../../src/lalg/mat/ge/lib.hpp" | ||
| 10 | |||
| 11 | using namespace tifa_libs; | ||
| 12 | CEXP u32 MOD = 998244353; | ||
| 13 | |||
| 14 | #include "../../../src/math/ds/mint/ms64/lib.hpp" | ||
| 15 | |||
| 16 | using namespace tifa_libs; | ||
| 17 | using mint = mint_ms64<MOD>; | ||
| 18 | |||
| 19 | 16 | int main() { | |
| 20 |
1/2✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
|
16 | std::cin.tie(nullptr)->std::ios::sync_with_stdio(false); |
| 21 | u32 n, m; | ||
| 22 |
2/4✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
|
16 | std::cin >> n >> m; |
| 23 | 16 | auto fact = gen_fact<mint>(m + 1); | |
| 24 | 16 | alist<void, degin_tag, degout_tag, arc_cnt_tag> g(n); | |
| 25 | 16 | u32 start = 0; | |
| 26 |
2/2✓ Branch 0 taken 2400022 times.
✓ Branch 1 taken 16 times.
|
2400038 | for (u32 i = 0, u, v; i < m; ++i) { |
| 27 |
2/4✓ Branch 1 taken 2400022 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2400022 times.
✗ Branch 5 not taken.
|
2400022 | std::cin >> u >> v; |
| 28 | 2400022 | g.add_arc(u, v); | |
| 29 | 2400022 | start = u; | |
| 30 | } | ||
| 31 |
2/2✓ Branch 1 taken 5 times.
✓ Branch 2 taken 11 times.
|
16 | if (!is_eulerian(g)) { |
| 32 |
1/2✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
|
5 | std::cout << "0\n"; |
| 33 | 5 | return 0; | |
| 34 | } | ||
| 35 |
1/2✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
|
11 | vecb vis(n); |
| 36 | 2668 | auto f = [&](auto&& f, u32 x) -> void { | |
| 37 |
2/2✓ Branch 6 taken 1600020 times.
✓ Branch 7 taken 2668 times.
|
1602688 | for (auto v : g[x]) |
| 38 |
5/8✓ Branch 2 taken 1600020 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2657 times.
✓ Branch 6 taken 1597363 times.
✓ Branch 9 taken 2657 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 2657 times.
✗ Branch 15 not taken.
|
1600020 | if (!vis[v]) vis[v] = 1, f(f, v); |
| 39 | 2668 | }; | |
| 40 |
2/4✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 11 times.
✗ Branch 6 not taken.
|
11 | vis[start] = 1, f(f, start); |
| 41 |
1/2✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
|
11 | vecu ids(n, -1_u32), inv_ids; |
| 42 | 11 | u32 cnt_ids = 0; | |
| 43 |
2/2✓ Branch 0 taken 4017 times.
✓ Branch 1 taken 11 times.
|
4028 | flt_ (u32, i, 0, n) |
| 44 |
4/6✓ Branch 1 taken 4017 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2668 times.
✓ Branch 5 taken 1349 times.
✓ Branch 8 taken 2668 times.
✗ Branch 9 not taken.
|
4017 | if (vis[i]) ids[i] = cnt_ids++, inv_ids.push_back(i); |
| 45 | 11 | amat<mint> mat(cnt_ids); | |
| 46 |
2/2✓ Branch 0 taken 2668 times.
✓ Branch 1 taken 11 times.
|
2679 | flt_ (u32, id, 0, cnt_ids) { |
| 47 | 2668 | auto& tos = g[inv_ids[id]]; | |
| 48 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2668 times.
|
2668 | if (tos.empty()) continue; |
| 49 |
1/2✓ Branch 1 taken 2668 times.
✗ Branch 2 not taken.
|
2668 | tifa_libs::sort(tos); |
| 50 | 2668 | u32 cnt = 1, pre = tos[0]; | |
| 51 |
2/2✓ Branch 1 taken 1597352 times.
✓ Branch 2 taken 2668 times.
|
1600020 | flt_ (u32, j, 1, (u32)tos.size()) |
| 52 |
2/2✓ Branch 2 taken 664087 times.
✓ Branch 3 taken 933265 times.
|
1597352 | if (tos[j] != pre) mat.add_arc(id, ids[pre], cnt), pre = tos[j], cnt = 1; |
| 53 | 933265 | else ++cnt; | |
| 54 | 2668 | mat.add_arc(id, ids[pre], cnt); | |
| 55 | } | ||
| 56 | 2261498 | auto is_0 = [](cT_(mint) x) { return x.val() == 0; }; | |
| 57 | 10 | auto ge = [&](matrix<mint>& A, bool clear_u) { return ge_mat<mint, decltype(is_0), true>(A, is_0, clear_u); }; | |
| 58 |
1/2✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
|
11 | mint ans = kirchhoff<true>(mat, ids[start], ge); |
| 59 |
2/2✓ Branch 0 taken 2668 times.
✓ Branch 1 taken 11 times.
|
2679 | flt_ (u32, i, 0, cnt_ids) |
| 60 |
1/2✓ Branch 2 taken 2668 times.
✗ Branch 3 not taken.
|
2668 | if (g.dout[inv_ids[i]]) ans *= fact[g.dout[inv_ids[i]] - 1]; |
| 61 |
1/2✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
|
11 | std::cout << ans << '\n'; |
| 62 | 11 | return 0; | |
| 63 | 16 | } | |
| 64 |