問題一覧 > 通常問題

No.2794 I Love EDPC-T

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : 箱星箱星 / テスター : ecotteaecottea
5 ProblemId : 9131 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-31 20:34:49

問題文

長さ $N-1$ の文字列 $s$ が与えられます。$s$ は <, > からなります。

$(1,2,\ldots,N)$ の順列 $(p_1,p_2,\ldots,p_N)$ であって、次の条件をすべて満たすものは何通りありますか。$998244353$ で割った余りを求めてください。

  • 各 $i \ (1\le i\le N-1)$ に対して、$s$ の $i$ 文字目が < ならば $p_i\lt p_{i+1}$ であり、> ならば $p_i\gt p_{i+1}$ である。
  • $(p_1,p_2,\ldots,p_N)$ の最長増加部分列の長さは $2$ である。

制約

  • $N$ は $2$ 以上 $2\times 10^5$ 以下の整数
  • $s$ は <, > からなる長さ $N-1$ の文字列

入力

入力は以下の形式で標準入力から与えられます。
$N$
$s$

出力

条件をすべて満たす順列の個数を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
4
<><
出力
2

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

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

サンプル3
入力
35
><>><>>><>>>><>>>>><>>>>>><>>>>>>>
出力
592821357

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

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