問題一覧 > 通常問題

No.1821 LEQ-GEQ Permutations

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : nok0nok0 / テスター : rianoriano saksak
7 ProblemId : 7539 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-21 18:57:42

問題文

0, 1 からなる長さ $N$ の文字列 $S$ が与えられます。

二つの長さ $N$ の順列の組 $(P,Q)$ であって、以下の条件を満たすものの個数を $\bmod 998244353$ で求めてください。

  • 任意の $i\ (1 \le i \le N)$ について、 $S_i =$0 ならば $P_i \leq Q_i$, $S_i =$1 ならば $P_i \geq Q_i$ が成り立つ。

制約

  • $1\le N \le 5000$
  • $S$ は 0,1 からなる長さ $N$ の文字列である。

入力

$N$
$S$

出力

条件を満たす二つの長さ $N$ の順列の組 $(P,Q)$ の個数を $\bmod{998244353}$ で出力してください。

サンプル

サンプル1
入力
3
001
出力
14

条件を満たす組 $(P,Q)$ は以下の $14$ 通りです。

  • $((1,2,3),(1,2,3))$
  • $((1,2,3),(1,3,2))$
  • $((1,2,3),(2,3,1))$
  • $((1,2,3),(3,2,1))$
  • $((1,3,2),(1,3,2))$
  • $((1,3,2),(2,3,1))$
  • $((2,1,3),(2,1,3))$
  • $((2,1,3),(2,3,1))$
  • $((2,1,3),(3,1,2))$
  • $((2,1,3),(3,2,1))$
  • $((2,3,1),(2,3,1))$
  • $((3,1,2),(3,1,2))$
  • $((3,1,2),(3,2,1))$
  • $((3,2,1),(3,2,1))$

サンプル2
入力
3
111
出力
6

条件を満たす組 $(P,Q)$ は以下の $6$ 通りです。

  • $((1,2,3),(1,2,3))$
  • $((1,3,2),(1,3,2))$
  • $((2,1,3),(2,1,3))$
  • $((2,3,1),(2,3,1))$
  • $((3,1,2),(3,1,2))$
  • $((3,2,1),(3,2,1))$

サンプル3
入力
10
1010110001
出力
808663691

$\bmod 998244353$ で出力することに注意してください。

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