問題一覧 > 教育的問題

No.2274 三角彩色

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : 👑 p-adicp-adic / テスター : ecotteaecottea
0 ProblemId : 9231 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-02 18:08:50

問題文

入力に $4$ 個の正整数 $N, M, B, Q$ と、$N$ 頂点 $M$ 辺を持つ無向多重グラフ $G$ と $Q$ 個のクエリ(後述)が与えられます。

ただしここでの無向多重グラフは自己ループを持たないものを指します。

 

$G$ の頂点を $N$ 未満の各非負整数 $n$ で番号付け「頂点 $n$」と呼び、$G$ の辺を $M$ 未満の各非負整数 $m$ で番号付け「辺 $m$」と呼び、辺 $m$ の結ぶ $2$ 頂点を頂点 $i_m$ と頂点 $j_m$ ($i_m, j_m$ は $0 \leq i_m < j_m < N$ を満たす整数)と置きます。

$3$ 個の $M$ 未満の非負整数 $m_0, m_1, m_2$ に対し、辺 $m_0$ と辺 $m_1$ と辺 $m_2$ が $3$ 頂点を通る閉路をなすということをここでは $\triangle m_0 m_1 m_2$ と書き表します。

各クエリは、$3$ 個の $M$ 未満の非負整数 $m_0, m_1, m_2$ の組 $(m_0,m_1,m_2)$ であって以下の $2$ 条件を満たすものです:

  • $m_0 < m_1 < m_2$
  • $\triangle m_0 m_1 m_2$

また辺 $m_0$ と辺 $m_1$ と辺 $m_2$ を「三角形 $(m_0,m_1,m_2)$ の $3$ 辺」と呼びます。

 

白と黒のみを用いた $G$ の辺の塗り分け方を考えます。塗り分け方という概念は正確には彩色という概念を用いて定義されます。(クリックで開く)

 

$G$ の辺全体の集合を $E$ と置き、白と黒に対応する $2$ つの集合 $W$ と $B$ を固定します。どのように固定しても良く、例えば $W = \{\}$、$B = \{\{\}\}$ などのように定めるのが一般的な方法の1つです。

$E$ の $\{W,B\}$ 彩色とは、$E$ から $\{W,B\}$ への写像のことです。特に $W = \{\}$ かつ $B = \{\{\}\}$ と定める場合、$\{W,B\}$ 彩色は $2$ 彩色と呼ばれます。$E$ の $\{W,B\}$ 彩色が与えられた時、$W$ に値を持つ辺は白で塗られると解釈し $B$ に値を持つ辺は黒で塗られると解釈することで、$G$ の辺の(白と黒による)塗り分け方という概念を $E$ の $\{W,B\}$ 彩色そのものとして数学的に定式化します。

この定式化においては「辺を塗る順番」などは考慮されません。特に写像の一致の必要十分条件を考えることで、$2$ つの塗り分け方 $f$ と $g$ が等しいことと $G$ の任意の辺 $e$ に対し $f$ における $e$ の色と $g$ における $e$ の色が等しいということが同値であることが分かります。

 

塗り分け方は全部で $2^M$ 通りありますが、このうち次の条件を満たす塗り分け方を「良い塗り分け方」と呼びます:

  • $N$ 未満の任意の非負整数 $n$ に対し、頂点 $n$ を端点に持つ白い辺の個数は偶数である。

良い塗り分け方の集合 $S$ と $T$ を以下の手続きで定める時、最終的な $S$ と $T$ の要素数を $B$ で割った余りがそれぞれいくつになるか答えてください。

  1. まず最初に、$S$ を「少なくとも $1$ 本の辺を白く塗る良い塗り分け方」全体の集合と定め、$T$ を「全ての辺を黒く塗る良い塗り分け方」のみからなる集合と定めます。
  2. そしてクエリ $(m_0,m_1,m_2)$ が与えられるたび、次の条件を満たす良い塗り分け方 $c$ であって $S$ に属すものを全て $S$ から削除し $T$ に追加します:
    • $T$ に属す良い塗り分け方 $c'$ であって、$c'$ から三角形 $(m_0,m_1,m_2)$ の $3$ 辺の色を全て変更して得られる塗り分け方が $c$ であるものが存在する。

入力

入力は以下の形式で標準入力から与えられます:

  • $1$ 行目に $N, M, B, Q$ が半角空白区切りで与えられます。
  • $M$ 未満の各非負整数 $m$ に対し、$2 + m$ 行目に $i_m, j_m$ が半角空白区切りで与えられます。
  • $Q$ 以下の各正整数 $q$ に対し、$1 + M + q$ 行目に $q$ 個目のクエリの各成分が半角空白区切りで与えられます。

制約

入力は以下の制約を満たします:

  • $N$ は $3 \leq N \leq 10^{18}$ を満たす整数
  • $M$ は $3 \leq M \leq 4 \times 10^2$ を満たす整数
  • $B$ は $2 \leq B \leq 10^9$ を満たす整数
  • $Q$ は $1 \leq Q \leq 10^3$ を満たす整数
  • $M$ 未満の各非負整数 $m$ に対し、$i_m, j_m$ は $0 \leq i_m < j_m < N$ を満たす整数
  • $Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリ $(m_0,m_1,m_2)$ の各成分 $m_0, m_1, m_2$ は $0 \leq m_0 < m_1 < m_2 < M$ と $\triangle m_0 m_1 m_2$ を満たす整数

出力

最終的な $S$ と $T$ の要素数を $B$ で割った余りを半角空白区切りで $1$ 行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3 2 1
0 1
1 2
0 2
0 1 2
出力
0 0

最初 $S$ には

  • 全ての辺を白で塗る良い塗り分け方

だけが属し、$T$ には

  • 全ての辺を黒で塗る良い塗り分け方

だけが属しています。クエリ $(0,1,2)$ が与えられると、後者から三角形 $(0,1,2)$ の $3$ 辺の色を全て変更して得られる塗り方である

  • 全ての辺を白で塗る良い塗り分け方

が $S$ から削除され、$T$ に追加されます。

従って最終的な $S$ と $T$ の要素数は $0$ 個と $2$ 個であり、これらを $B = 2$ で割った余りは $0$ と $0$ です。

サンプル2
入力
3 4 3 1
0 1
0 1
1 2
0 2
0 2 3

$2$ 頂点を複数の辺が結ぶこともあります。

出力
2 2

最初 $S$ には

  • 辺 $0$ を黒で塗り残りを白で塗る良い塗り分け方
  • 辺 $1$ を黒で塗り残りを白で塗る良い塗り分け方
  • 辺 $2$ と辺 $3$ を黒で塗り残りを白で塗る良い塗り分け方

が属し、$T$ には

  • 全ての辺を黒で塗る良い塗り分け方

だけが属しています。クエリ $(0,2,3)$ が与えられると、$T$ に属す良い塗り分け方から三角形 $(0,2,3)$ の $3$ 辺の色を全て変更して得られる塗り分け方である

  • 辺 $1$ を黒で塗り残りを白で塗る良い塗り分け方

が $S$ から削除され $T$ に追加されます。

従って最終的な $S$ と $T$ の要素数はそれぞれ $2$ 個と $2$ 個であり、それらを $B = 3$ で割った余りは $2$ と $2$ です。

サンプル3
入力
3 4 3 2
0 1
0 1
1 2
0 2
0 2 3
1 2 3
出力
0 1

$1$ つ目のクエリを処理した後の状況はサンプルケース2の最終的な状況と同じです。従って $S$ には

  • 辺 $0$ を黒で塗り残りを白で塗る良い塗り分け方
  • 辺 $2$ と辺 $3$ を黒で塗り残りを白で塗る良い塗り分け方

が属し、$T$ には

  • 全ての辺を黒で塗る良い塗り分け方
  • 辺 $1$ を黒で塗り残りを白で塗る良い塗り分け方

が属しています。$2$ つ目のクエリ $(1,2,3)$ が与えられると、$T$ に属す良い塗り分け方から三角形 $(1,2,3)$ の $3$ 辺の色を全て変更して得られる良い塗り分け方である

  • 辺 $0$ を黒で塗り残りを白で塗る良い塗り分け方
  • 辺 $2$ と辺 $3$ を黒で塗り残りを白で塗る良い塗り分け方

が $S$ から削除され $T$ に追加されます。

従って最終的な $S$ と $T$ の要素数はそれぞれ $0$ 個と $4$ 個であり、それらを $B = 3$ で割った余りは $0$ と $1$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。