問題一覧 > 通常問題

No.1303 Inconvenient Kingdom

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 16
作問者 : nok0 / テスター : 👑 hamamu Kite_kuma
お気に入りにしたユーザー ProblemId : 5344 / 自分の提出
問題文最終更新日: 2020-11-26 20:01:36
Inconvenient Kingdom
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 276 (順位表) の他の問題:

Problem Statement

The Kingdom of yuki has $N$ cities numbered from $1$ to $N$.

There are currently plans to build several roads, each bidirectionally connecting $2$ distinct cities. At this moment, there are no roads connecting the cities.

You are given $M$ road construction plans numbered from $1$ to $M$. The $i$-th road construction plan lists city $u_i$ and city $v_i$.

You may select between $0$ and $M$ distinct road construction plans, inclusive, and perform the following operation for each selected road construction plan.

  • Letting $i$ be the number of the selected road construction plan, build a road bidirectionally connecting city $u_i$ and city $v_i$.

    • After finishing the above operations, you may perform the following operation between $0$ and $1$ times, inclusive.

  • Select two distinct cities. Letting $x$ and $y$ be the selected cities, build a road bidirectionally connecting city $x$ and city $y$. However, if a road bidirectionally connecting city $x$ and city $y$ already exists, no road is built.

    • Now, define the inconvenience as follows.

    Inconvenience $:= \displaystyle\sum_{i=1}^{N}$(the number of cities not connected to city $i$)

    Your goal is to minimize the inconvenience by building roads optimally. Find the minimum achievable inconvenience.

    Also, among the "ways of building roads" that achieve the minimum inconvenience, find the number of distinct "ways of building roads" in which the number of roads built is minimum.

    Since the number of "ways of building roads" satisfying the conditions can be very large, output it modulo $998244353$.


    Note: Definition of connectivity

    When one city can be reached from another city by traversing some number of roads, those cities are said to be connected. Also, every city is considered to be connected to itself.

    Note: Definition of distinct "ways of building roads"

    Two "ways of building roads" are defined to be distinct if there exist cities $i$ and $j$ such that a road connecting city $i$ and city $j$ exists in one way of building and no road connecting city $i$ and city $j$ exists in the other way of building. Note that it does not matter by which operation a road was built.

    Constraints

    • All inputs are integers.
    • $2 \le N\le 100$
    • $0 \le M\le \frac{N (N - 1)} {2}$
    • $1 \le u_i < v_i\le N$
    • If $i \neq j$, then $u_i \neq u_j$ or $v_i \neq v_j$ holds.

    Input

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

    Output

    On the first line, output the minimum achievable inconvenience.

    On the second line, output the number, modulo $998244353$, of distinct "ways of building roads" in which the number of roads built is minimum among those that achieve the minimum inconvenience.

    Sample

    Sample 1
    Input
    3 1
1 2
    Output
    0
2

    An inconvenience of $0$ can be achieved by building $1$ road between city $1$ and city $2$ according to the construction plan, and building $1$ road between city $3$ and either city $1$ or city $2$.

    Sample 2
    Input
    3 0
    Output
    4
3

    For example, if $1$ road is built between city $1$ and city $2$, the inconvenience is $1 + 1 + 2 = 4$, and this is the minimum.

    Sample 3
    Input
    3 2
1 2
1 3
    Output
    0
3

    An inconvenience of $0$ can be achieved.

    • Build $1$ road each between city $1$ and city $2$, and between city $1$ and city $3$
    • Build $1$ road each between city $1$ and city $2$, and between city $2$ and city $3$
    • Build $1$ road each between city $1$ and city $3$, and between city $2$ and city $3$
    These $3$ distinct ways of building are possible. Note that you do not have to perform the operation of building a road bidirectionally connecting any two distinct cities.

    Sample 4
    Input
    11 10
5 11
6 11
2 6
2 5
2 11
3 4
3 9
1 10
4 9
7 8
    Output
    64
288

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