問題一覧 > 通常問題

No.1937 Various Tournament

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : noya2noya2 / テスター : chineristACchineristAC tatyamtatyam
4 ProblemId : 7563 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-14 11:03:53

問題文

正整数 $N$ が与えられます。ただし、$N$ は $2,4,8,16$ のいずれかです。

$1,2,\dots ,N$ の番号がついた $N$ 人の参加者によるボクシングのトーナメント戦をします。 トーナメントは以下の方式で行われます。

  • $N$ 人の参加者をある順番で横一列に並べる。
  • 左から奇数番目の参加者は右隣の参加者と $1$ 度だけボクシングの試合を行い、勝った人は列に残り負けた人は列から脱落する。 列に残った人が $1$ 人になるまで繰り返す。
  • 最後に残った $1$ 人が優勝者となり、トーナメントを終了する。

Noya君は、任意の参加者の他の参加者に対する相性を調べ、$N$ 行 $N$ 列からなる表 $S$ を作成しました。 この表は以下のことを表します。

    任意の $i,j\ (1\le i\lt j\le N)$ について、$S_{i,\ j}=1$ のとき参加者 $i$ は参加者 $j$ に必ず勝ち、 $S_{i,\ j}=0$ のとき参加者 $i$ は参加者 $j$ に必ず負ける。

ただし、$1\le i,\ j\le N$ について $i\neq j$ ならば $S_{i,\ j} + S_{j,\ i}=1$ 、$i=j$ ならば $S_{i,\ j}=0$ が保証されます。


$N$ 人の参加者を横一列に並べる方法は $N!$ 通りありますが、このうち参加者 $k$ が優勝者となる方法は何通りありますか。

$k=1,2,\dots ,N$ について答えを出力してください。

制約

  • 入力はすべて整数
  • $N$ は $2,4,8,16$ のいずれか
  • $S_{i,j}$ は $0,1$ のいずれか
  • $S_{i,j} + S_{j,i} = 1\ (i\neq j)$
  • $S_{i,i}=0$
  • 入力

    $N$
    $S_{1,1}$ $S_{1,2}$ $\dots$ $S_{1,N}$
    $\vdots$
    $S_{N,1}$ $S_{N,2}$ $\dots$ $S_{N,N}$
    

    出力

    $N$ 行出力してください。$i$ 行目には $k=i$ のときの答えを出力してください。

    サンプル

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

    参加者 $1$ は参加者 $2$ に必ず勝ちます。参加者の並べ方は $(1,2),(2,1)$ の $2$ 通りありますが、 いずれも参加者 $1$ が優勝します。

    サンプル2
    入力
    4
    0 1 0 1
    0 0 1 0
    1 0 0 1
    0 1 0 0
    出力
    8
    0
    16
    0

    残念ながら参加者 $2,4$ の勝ち目はありません。

    サンプル3
    入力
    8
    0 1 0 1 0 1 0 1
    0 0 1 0 1 0 1 0
    1 0 0 1 0 1 0 1
    0 1 0 0 1 0 1 0
    1 0 1 0 0 1 0 1
    0 1 0 1 0 0 1 0
    1 0 1 0 1 0 0 1
    0 1 0 1 0 1 0 0
    出力
    4480
    4352
    5888
    2944
    8320
    1664
    11648
    1024

    誰が優勝するのかは、参加者の並べ方次第です。

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