No.2899 Taffy Permutation
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 :
lgswdn
/ テスター :
👑 
獅子座じゃない人
タグ : / 解いたユーザー数 35
作問者 :
lgswdn
/ テスター :
👑 問題文最終更新日: 2024-09-17 22:53:06
問題文
$0$ と $1$ からなる文字列 $s_1s_2\dots s_N$ が与えられます。以下の条件を満たす $[1,2,\dots,N]$ の順列 $p$ の個数を $998244353$ で割った余りを求めてください。
- $s_i=0,s_j=1$ かつ $i<j$ を満たす任意の組 $(i,j)$ について、 $p_i<p_j$ を満たす。
入力
$N$ $s_1s_2\dots s_N$
- $N$ は整数
- $1\le N\le 2000$
- $s_i$ は $0$ または $1$
出力
答えを $998244353$ で割った余りを出力し、最後に改行してください。
サンプル
サンプル1
入力
4 0101
出力
5
$[1,2,3,4],[1,3,2,4],[1,4,2,3],[2,3,1,4],[2,4,1,3]$ の $5$ 個が条件を満たします。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。