AOJ3369 Namori Counting (行列木定理)
(Test/Manual/aoj3369.test.cpp)

View this file on GitHub
Last update: 2024-06-25 21:21:56+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/3369/judge/9369476/C++17

$M - N$ 本の辺を削除してから頂点に色を塗ると考えて良い。

解はグラフの全域木の数に $M - (N - 1)$ をかけた値である。なもりグラフは全域木に辺を一本追加することで作ることができる。全域木の数 $\times M - (N - 1)$ という値は各なもりグラフを丁度閉路サイズ回重複して数え上げた値となっている。

グラフの全域木の数

単純なグラフ$G(V, E)$に対して $N$ 行 $N$ 列の行列 $L$ を以下のように定義する。

頂点 $v$ の次数が $d_{v}$ なら、 $L_{vv} = d_{v}$
$u\ne v$ に対して、 $L_{uv}$ を頂点対 $(u, v)$ を直接結ぶ辺の数を $-1$ 倍したもの。

この $L$ の任意の余因子が $G$ の全域木の数に一致する。 (行列木定理)

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AOJ3369 Namori Counting
 * https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/3369/judge/9369476/C++17
 */

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/LinearAlgebra/Matrix.hpp"
#include "../../Src/Algebra/Ring/UsualRing.hpp"
#include "atcoder/modint"

#include <iostream>

using namespace zawa;
using mint = atcoder::modint998244353;
using Mat = Matrix<UsualRing<mint>>;

int main() {
    std::cout << "Hello World" << '\n';
    // SetFastIO();
    // int N, M;
    // std::cin >> N >> M;
    // Mat g(N, N);
    // for (int _{} ; _ < M ; _++) {
    //     int u, v;
    //     std::cin >> u >> v;
    //     u--; v--;
    //     g[u][u]++;
    //     g[v][v]++;
    //     g[u][v] = g[v][u] = mint{-1};
    // }
    // mint ans{g.cofactor(0, 0) * mint{M - N + 1}};
    // std::cout << ans.val() << '\n';
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header

AOJ3369 Namori Counting (行列木定理) (Test/Manual/aoj3369.test.cpp)

Depends on

Code

AOJ3369 Namori Counting (行列木定理)
(Test/Manual/aoj3369.test.cpp)