問題一覧 > 通常問題

No.1821 LEQ-GEQ Permutations

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

問題文

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

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

  • 任意の i (1≤i≤N) について、 Si=0 ならば Pi≤Qi, Si=1 ならば Pi≥Qi が成り立つ。

制約

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

入力

N
S

出力

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

サンプル

サンプル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

mod998244353 で出力することに注意してください。

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