問題一覧 > 通常問題

No.1303 Inconvenient Kingdom

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : nok0nok0 / テスター : hamamuhamamu Kite_kumaKite_kuma
5 ProblemId : 5344 / 出題時の順位表
問題文最終更新日: 2020-11-26 20:01:36

問題文

yuki王国には、 $1$ から $N$ までの番号がついた $N$ 個の都市があります。

現在、 $2$ つの相異なる都市を双方向に結ぶ道路をいくつか建設することが予定されています。現時点では、都市を結ぶ道路はありません。

$1$ から $M$ までの番号がついた $M$ 個の道路建設予定が与えられます。 $i$ 番目の道路建設予定には、都市 $u_i$ と都市 $v_i$ が書かれています。

あなたは $0$ 個以上 $M$ 個以下の異なる道路建設予定を選択し、選択した道路建設予定それぞれについて以下の操作を行うことができます。

  • 選択した道路建設予定の番号を $i$ として、都市 $u_i$ と都市 $v_i$ を双方向に結ぶ道路を建設する。
  • 以上の操作を終えた後、あなたは $0$ 回以上 $1$ 回以下、以下の操作を行うことができます。

  • 相異なる都市を二つ選択する。選択した都市を $x$ と $y$ として、都市 $x$ と都市 $y$ を双方向に結ぶ道路を建設する。ただし、すでに都市 $x$ と都市 $y$ を双方向に結ぶ道路が存在する場合、道路の建設は行わない。
  • さて、ここで不便度を以下のように定義します。

    不便度 $:= \displaystyle\sum_{i=1}^{N}$(都市 $i$ と連結でない都市の個数)

    あなたの目標は最適に道路を建設することで不便度を最小にすることです。達成可能な不便度の最小値を求めてください。

    また、不便度最小を達成する「道路の建設方法」の中で、建設する道路の本数が最小であるような 異なる「道路の建設方法」の個数も求めてください。

    条件を満たす「道路の建設方法」の個数は非常に大きくなる可能性があるので、 $998244353$ で割った余りを答えてください。


    注:連結の定義

    ある都市から別の都市に何本かの道路を通って到達できるとき、それらの都市は連結であるとします。また、すべての都市はそれ自身と連結であるとみなします。

    注:異なる「道路の建設方法」の定義

    二つの「道路の建設方法」について、ある都市 $i$ と $j$ が存在し、 一方の建設方法では都市 $i$ と 都市 $j$ を結ぶ道路が存在して、もう一方の建設方法では都市 $i$ と 都市 $j$ を結ぶ道路が存在しない場合、 それらの二つの「道路の建設方法」は異なると定義します。どちらの操作で道路を建設したかは区別しないことに注意してください。

    制約

    • 入力は全て整数である。
    • $2 \le N\le 100$
    • $0 \le M\le \frac{N (N - 1)} {2}$
    • $1 \le u_i < v_i\le N$
    • $i \neq j$ ならば $u_i \neq u_j$ または $v_i \neq v_j$ を満たす。

    入力

    $N\  M$
    $u_1\ v_1$
    $u_2\ v_2$
    $\vdots$
    $u_M\ v_M$
    

    出力

    一行目には、達成できる不便度の最小値を出力してください。

    二行目には、不便度最小を達成する「道路の建設方法」の中で、建設する道路の本数が最小であるような 異なる「道路の建設方法」の個数を $998244353$ で割った余りを出力してください。

    サンプル

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

    建設予定に従って都市 $1$ と都市 $2$ 間に道路を $1$ 本建設して、 都市 $1$ か都市 $2$ のいずれかと都市 $3$ 間に道路を $1$ 本建設することで不便度 $0$ を達成できます。

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

    例えば都市 $1$ と都市 $2$ 間に道路を $1$ 本建設すると、 不便度は $1 + 1 + 2 = 4$ となり、これが最小です。

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

    不便度 $0$ を達成することができます。

    • 都市 $1$ と都市 $2$ 間、都市 $1$ と都市 $3$ 間に道路を $1$ 本ずつ建設する
    • 都市 $1$ と都市 $2$ 間、都市 $2$ と都市 $3$ 間に道路を $1$ 本ずつ建設する
    • 都市 $1$ と都市 $3$ 間、都市 $2$ と都市 $3$ 間に道路を $1$ 本ずつ建設する
    の $3$ 個の異なる建設方法が考えられます。任意の異なる二つの都市間を双方向に結ぶ道路を建設する操作は行わなくても構わないことに注意してください。

    サンプル4
    入力
    11 10
    5 11
    6 11
    2 6
    2 5
    2 11
    3 4
    3 9
    1 10
    4 9
    7 8
    出力
    64
    288

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