No.2040 010-1 Deletion
タグ : / 解いたユーザー数 38
作問者 :
milkcoffee
/ テスター :
nok0
riano
Problem Statement
A string $T$ consisting of 0, 1 is called a good string if $T$ satisfies the following condition.
- By repeatedly choosing one of the following operations and performing it on $T$ any number of times, $T$ can be made into the empty string.
- Delete a string
1contained in $T$. After the deletion, the string formed by joining the parts before and after it becomes the new $T$. - Delete a string
010contained in $T$. After the deletion, the string formed by joining the parts before and after it becomes the new $T$.
- Delete a string
For example, 0110 and 01011010 are good strings, but 000 and 0001 are not good strings.
You are given a string $S$ of length $N$ consisting of 0, 1, ?.
Find the number, modulo $998244353$, of ways to replace each ? with 0 or 1 such that the result is a good string.
Input
$N$ $S$
- $1 \leq N \leq 1500$
- $N$ is an integer.
- $S$ is a string of length $N$ consisting of
0,1,?.
Output
Print the answer modulo $998244353$ as an integer.
Sample
Sample 1
Input
6 010???
Output
3
The result is a good string only for 010010, 010100, 010111.
Sample 2
Input
4 000?
Output
0
No good string can be made.
Sample 3
Input
1 ?
Output
1
Sample 4
Input
40 ???0????1???????1??????0????1???????1???
Output
883469710
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。