maspypy
maspypy
## 問題名 辺重みのある (N, M) 有向グラフが与えられる。辺重みは非負とは限らない。 始点 $s$ が与えられる。N 行出力。各 $v$ に対して、次を出力 - walk がひとつも存在しない場合：`NONE` - 最短路長が存在する場合：最短長 - いくらでも小さい walk が存在する場合：`-INFINITY` ## 制約 (3000,3000) くらい？ ## 解法 Bellman Ford /...
Other Sponsored - 「第三回日本最強プログラマー学生選手権 -決勝-」 - 「第三回日本最強プログラマー学生選手権 -決勝- (オープンコンテスト)」 各問題名からのリンク先が、すべて「オープン」側になっています。 コンテスト名からのリンクは適切になっているみたいです。 （その他の「オープンコンテスト」も同様の状況っぽいです） これらは問題は同一ですし、Problems 上での AC 判定も同一ですが、順位表や提出の情報が異なるので、 正しくリンクされている方が親切かと思います。
# 問題概要 以下を、mod 2 で解け。 - Matrix Product：済 - Determinant of Matrix：済 - System of Linear Equations - Inverse Matrix：済 - Rank of Matrix # 問題名案 - Matrix Product (modulo...
[問題] $M\geq 1$ を満たす有向グラフが与えられる．Eulerian Circuits であって最初に通る辺が番号 $0$ の辺であるものを数える． [解法] BEST Theorem [想定揉めどころ] 「全頂点を通るものを数えよ」とするかどうか． https://judge.yosupo.jp/problem/eulerian_trail_directed ではこれはしなかった．しないでよい気がする． [制約] $N\leq 500$
[問題] （無向） $N$ 頂点 $M$ 辺の無向グラフが与えられる．全域木を数える．使う辺番号が違うなら違うとする． mod 998244353． （有向） $N$ 頂点 $M$ 辺の有向グラフが与えられる．根 $r$ も与えられる． $r$ を根とする有向全域木を数える．使う辺番号が違うなら違うとする． mod 998244353． [制約] $N\leq 500$ [解法] 行列木定理
## 問題概要 非負整数 $A_0, \ldots, A_{N-1}$, $B_0, \ldots, B_{N-1}$ が与えられる．非負整数列 $(x_i)$ で次を満たすものを mod 998244353 で数えよ． - $0\leq x_0 \leq \cdots \leq x_{N-1} < M$ - $A_i\leq x_i < B_i$ ##...
# 問題概要 整数 $q$ および素数 $p$ が与えられる。 $Q$ クエリに答えよ。 $n, r$ が与えられるので、 $q$ - 二項係数 $\binom{\mathbf{n}}{\mathbf{k}}_q$ を $\pmod{p}$ で求めよ。 # 制約 - $1\leq Q\leq 10^6$ - $1\leq p\leq 10^9$、素数 -...
# 問題概要 木がある。辺重みがある。 順列 $p_0, \ldots, p_{n-1}$ が与えられる。 $k=1,2,\ldots,n$ に対して次に答えよ： $S = \{p_0,\ldots,p_{k-1}\}$ とする。 $f(v) = \sum_{s\in S} dist(v, s)$ とするとき、 $\min_v f(v)$ を出力。 # 制約 $5\times 10^5$ とか？ #...
# 問題概要 $N$ 頂点 $M$ 辺のグラフが与えられる．彩色多項式を出力せよ． # 制約 - $1\leq N\leq 20$ - $0\leq M \leq 500$ - ループあり、多重辺あり # 解法 https://github.com/yosupo06/library-checker-problems/issues/975 を使うと、非空独立集合 $k$ 個に分割する方法が数えられるのでできる。 # 関連 - https://github.com/yosupo06/library-checker-problems/issues/975 -...
[問題概要] xor に関する F_2 ベクトル空間の共通部分の基底を一組出力せよ。 T テストケース 入出力形式： $n$ $u_0$ $\ldots$ $u_{n-1}$ $m$ $v_0$ $\ldots$ $v_{m-1}$ 入出力ともに基底 [制約] - $T\leq 10^5$ （入出力が大きくなるので、要調整） - $0\leq n, m \leq 30$ - $0\leq...