/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ 2N で + , - が N 個ずつからなる文字列 s に対して次の問題を考え、その答えを p(s) と書くことにします。
数直線上の x=1,2,3,\ldots , 2N の位置に 2N 個のボールが並んでおり、そのうち N 個は +1 の、残りの N 個は -1 の電荷を持ちます。ボールの持つ電荷の並び方は s によって表され、s の i 文字目が
+であれば x=i には +1 の電荷を持つボールが、-であれば x=i には -1 の電荷を持つボールが配置されていることを表します。それぞれのボールは、次の規則にしたがって、一斉に運動を始めます。ただし、数直線上でより小さい数が位置する方向を左、より大きい数が位置する方向を右と呼びます。
- 各ボールに対して、各時点で F を次の式で定める
F=\lbrace (自身より真に左に存在するボールの電荷の総和) - (自身より真に右に存在するボールの電荷の総和) \rbrace \times (自身の電荷)- 各ボールは各時点で、F が正であれば右に、負であれば左に、毎秒 1 の速さで動く
- 同時に同じ座標に電荷 +1 のボールと電荷 -1 のボールが存在した場合、両者は打ち消しあって消滅する
このとき、それぞれのボールが運動を始めてから消滅するまでに移動した距離（消滅した座標と初めの座標の差の絶対値）の総和はいくつでしょうか。
長さ 2N で、+ , - , ? からなる文字列 T が与えられます。T の ? を + または - に置換することで得られる、 + , - が N 個ずつからなる文字列 s 全てについての p(s) の総和を 998244353 で割った余りを求めてください。
なお、与えられた制約と運動の規則の下で、有限の時間内に全てのボールが消滅すること、ボールが消滅しない限り各ボールの F の値が 0 にならないこと、3 つ以上のボールが同時に同じ座標に位置する瞬間が無いこと、および p(s) が整数になることが示せます。
制約
- 1\leq N\leq 3000
- N は整数である
- |T|=2N
- T の各文字は
+,-,?のいずれかであり、+と-はそれぞれ N 個以下である
入力
入力は以下の形式で標準入力から与えられる。
N T
出力
答えを 998244353 で割った余りを整数で出力せよ。
入力例 1
2 +??-
出力例 1
6
T から得られる文字列 s として、 ++-- と +-+- が考えられます。
++-- について、運動を開始した時点では各ボールの左右の電荷の総和、および F の値は次のようになります。
したがって、x=1,2 のボールは右に、x=3,4 のボールは左に動き始めます。
この場合、各ボールはその後運動の向きを変えることなく、 0.5 秒後に x=2,3 にあったボールが x=2.5 で、1.5 秒後に x=1,4 にあったボールが x=2.5 でそれぞれ消滅します。
この間に、x=2,3 にあったボールは 0.5 ずつ、x=1,4 にあったボールは 1.5 ずつの距離を移動しているため、p( ++-- )=4 です。
同様に観察すると p( +-+- )=2 であることが分かるため、求める p(s) の総和は 6 となります。
入力例 2
17 ??????????????????????????????????
出力例 2
285212526
p(s) の総和を 998244353 で割った余りを出力してください。
Score : 600 points
Problem Statement
Consider the following problem for a string s of length 2N formed by N + and N -, and let p(s) denote the answer.
There are 2N balls lined up at positions x=1,2,3,\ldots , 2N on a number line, of which N have a charge of +1 and the remaining N have a charge of -1. The arrangement of the charges of the balls is represented by s. If the i-th character of s is
+, a ball with a charge of +1 is placed at x=i; if it is-, a ball with a charge of -1 is placed at x=i.Each ball starts motion simultaneously according to the following rules. Here, we call the direction where smaller numbers are located on the number line "left", and the direction where larger numbers are located "right".
- For each ball, define F at each moment by the following formula:
F=\lbrace (the sum of the charges of the balls strictly to the left of itself) - (the sum of the charges of the balls strictly to the right of itself) \rbrace \times (the charge of itself).- At each moment, each ball moves to the right if F is positive, and to the left if F is negative, at a speed of 1 per second.
- If a ball with a charge of +1 and a ball with a charge of -1 exist at the same coordinate simultaneously, they cancel out each other and disappear.
Then, what is the sum of the distances moved by the balls after they start motion and before they disappear (the distance moved by a ball is the absolute difference between the coordinates where it starts and where it disappears)?
You are given a string T of length 2N consisting of +, -, and ?. Find the sum of p(s) over all strings s formed by N + and N - that can be obtained by replacing each ? in T with + or -, modulo 998244353.
Under the given constraints and the rules of motion, it can be shown that all balls disappear in finite time, that the value of F for each ball does not become 0 until that ball disappears, that there is no moment when three or more balls are at the same coordinate simultaneously, and that p(s) is an integer.
Constraints
- 1\leq N\leq 3000
- N is an integer.
- |T|=2N
- Each character of T is either
+,-, or?, and there are at most N+and at most N-.
Input
The input is given from Standard Input in the following format:
N T
Output
Print the answer modulo 998244353, as an integer.
Sample Input 1
2 +??-
Sample Output 1
6
The strings s that can be obtained from T are ++-- and +-+-.
For ++--, the sum of the charges of the balls to the left and right of each ball, and the value of F at the start of the motion are as follows:
Thus, the balls at x=1,2 start moving to the right, and the balls at x=3,4 start moving to the left.
Then, each ball continues to move in the same direction without changing its direction of motion, and the balls that started at x=2,3 disappear at x=2.5 after 0.5 seconds, and the balls that started at x=1,4 disappear at x=2.5 after 1.5 seconds.
During these times, the balls that started at x=2,3 move a distance of 0.5 each, and the balls that started at x=1,4 move a distance of 1.5 each, so p( ++-- )=4.
Similarly, it can be seen that p( +-+- )=2, so the sought sum of p(s) is 6.
Sample Input 2
17 ??????????????????????????????????
Sample Output 2
285212526
Be sure to print the sum of p(s) modulo 998244353.