AtCoder Beginner Contest 468
受限排列AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given an integer $N$ and a string $S$ of length $N$ consisting of o and x.
给定一个整数 $N$，以及一个由 o 和 x 组成、长度为 $N$ 的字符串 $S$。AI (CI翻译)
Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ satisfying the following condition.
求满足以下条件的排列 $P=(P_1,P_2,\ldots,P_N)$ 的数量，答案对 $998244353$ 取模。AI (CI翻译)
- For
$k=1,2,\ldots,N$, the following two are equivalent. $S_k=$o$P$contains a permutation of$(1,2,\ldots,k)$as a contiguous subsequence.
- 对于
$k=1,2,\ldots,N$，以下两项等价： $S_k=$o$P$中存在一个连续子序列，其元素构成$(1,2,\ldots,k)$的一个排列。
Constraints
约束条件
AI (CI翻译)$1\le N\le 2000$$S_i$is a string of length$N$consisting ofoandx.
$1\le N\le 2000$$S_i$是一个由o和x组成、长度为$N$的字符串。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
SN
SOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
3
oxo
Output #1
2
$P=(1,3,2),(2,3,1)$ satisfy the condition.
Input #2
7
xxxxxxx
Output #2
0
There is no $P$ satisfying the condition.
Input #3
15
oxxxoxxxxxooxxo
Output #3
1627648
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。