No.2899 Taffy Permutation
lgswdn
問題文最終更新日: 2024-09-17 22:53:06
English (AI translation)
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 447 オムニバス
(順位表)
の他の問題:
Problem Statement
You are given a string $s_1s_2\dots s_N$ consisting of $0$ and $1$. Find the number, modulo $998244353$, of permutations $p$ of $[1,2,\dots,N]$ that satisfy the following condition.
- For every pair $(i,j)$ such that $s_i=0,s_j=1$ and $i<j$, it holds that $p_i<p_j$.
Input
$N$ $s_1s_2\dots s_N$
- $N$ is an integer.
- $1\le N\le 2000$
- $s_i$ is $0$ or $1$.
Output
Output the answer modulo $998244353$, followed by a newline.
Sample
Sample 1
Input
4 0101
Output
5
The $5$ permutations $[1,2,3,4],[1,3,2,4],[1,4,2,3],[2,3,1,4],[2,4,1,3]$ satisfy the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。