問題一覧 > 通常問題

No.1904 Never giving up!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 : 👑 hitonanodehitonanode / テスター : SumitacchanSumitacchan
4 ProblemId : 6232 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 01:19:21

問題文

中身の見えない袋に $N$ 個のボールが入っています.全てのボールには一つの整数が書かれていて,$i$ 個目のボール($1 \le i \le N$)に書かれている整数は $A_i$ です.

あなたは袋から $N$ 個のボールを一個ずつ取り出すゲームに挑戦します.このとき,取り出したボールに書かれている整数が単調非減少(すなわち,$t$ 個目に取り出したボール $(1 \le t \le N)$ に書かれた整数を $B_t$ として,$B_t \le B_{t + 1}$ が $t = 1, \dots, N - 1$ 全てで成立)であればあなたの勝利です.逆に,ゲームのいずれかの時点で直前に取り出したボールより小さい番号のボールを取り出してしまった場合,あなたは全てのボールを袋に戻して中身をよく混ぜ,再度はじめからこのゲームに挑戦します.なお,ボールの形状は均一で,袋からボールを取り出す際に各ボールが選ばれる確率は全て等しいです.

あなたがこのゲームに一度勝利するまでに必要な挑戦回数の期待値を求めてください.答えは $4 \times 10^{18}$ 未満の整数になることが本問題の制約から証明できます.

入力

$N$
$A_1\ A_2\ \dots \ A_N$

  • $2 \le N \le 20$
  • $1 \le A_i \le N \, (1 \le i \le N)$
  • 入力は全て整数

出力

答えとなる整数を出力してください.最後に改行してください.

サンプル

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

袋からのボールの取り出し方は確率 $1/2$ ずつで $[1, 2]$ と $[2, 1]$ のいずれかとなり,$[1, 2]$ を引いた時点で勝利です.ゲーム $1$ 回目で初めて勝利する確率が $1/2$,$2$ 回目で初めて勝利する確率が $(1/2)^2$,$3$ 回目で初めて勝利する確率が $(1/2)^3$,... となり,期待値は $2$ 回です.

サンプル2
入力
5
5 2 2 2 2
出力
5

あなたは $5$ が書かれたボールを最後に取り出せばよく,ゲーム $1$ 回目で初めて勝利する確率は $1 / 5$ です.初めて勝利するまでの挑戦回数の期待値は $5$ 回と計算できます.

サンプル3
入力
20
10 9 8 7 6 5 4 3 1 2 12 11 13 14 16 15 18 17 20 19
出力
2432902008176640000

毎秒一回挑戦しても,一回勝利するまでにかかる時間の期待値は約 $771$ 億年です.

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