問題一覧 > 通常問題

No.1821 LEQ-GEQ Permutations

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 26
作問者 : nok0 / テスター : riano sak
お気に入りにしたユーザー ProblemId : 7539 / 自分の提出
問題文最終更新日: 2022-01-21 18:57:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 328 (順位表) の他の問題:

Problem Statement

You are given a string $S$ of length $N$ consisting of 0, 1.

Find the number, modulo $\bmod 998244353$, of pairs $(P,Q)$ of two permutations of length $N$ that satisfy the following condition.

  • For every $i\ (1 \le i \le N)$, if $S_i =$0 then $P_i \leq Q_i$ holds, and if $S_i =$1 then $P_i \geq Q_i$ holds.

Constraints

  • $1\le N \le 5000$
  • $S$ is a string of length $N$ consisting of 0,1.

Input

$N$
$S$

Output

Output the number, modulo $\bmod{998244353}$, of pairs $(P,Q)$ of two permutations of length $N$ that satisfy the condition.

Sample

Sample 1
Input
3
001
Output
14

The following $14$ pairs $(P,Q)$ satisfy the condition.

  • $((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))$

Sample 2
Input
3
111
Output
6

The following $6$ pairs $(P,Q)$ satisfy the condition.

  • $((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))$

Sample 3
Input
10
1010110001
Output
808663691

Note that the output must be taken modulo $\bmod 998244353$.

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