問題一覧 > 通常問題

No.2616 中央番目の中央値

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 77
作問者 : startcppstartcpp / テスター : 👑 p-adicp-adic
2 ProblemId : 7737 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-21 22:21:48

問題文

長さ $N$ の順列 $P = (P_1, \cdots, P_N)$ が与えられます。

$P$ の部分列 $p$ であって以下の条件を全て満たすものはいくつあるでしょうか？

  • 長さが奇数
  • $p$ の中央値が、$p$ のちょうど中央に位置する
答えを $998244353$ (素数) で割った余りを求めてください。

入力

$N$
$P_1$ $\cdots$ $P_N$
  • 入力は整数
  • $1 \le N \le 300000$
  • $(P_1, \cdots, P_N)$ は $(1, 2, \cdots, N)$ を並べ替えた順列である。

出力

答えを $998244353$ で割った余りを求めてください。

サンプル

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

$(4), (2), (3), (1), (4, 2, 1), (4, 3, 1)$ の $6$ 通りが条件を満たします。

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

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