P5565 [Celeste-B] Farewell to Mount Celeste

> Sever the Skyline > > Black Moonrise > > Good Karma > > Golden Feather > > Mirror Magic > > Center of the Earth > > No More Running > > And... > > Say Goodbye.

At the farewell banquet, the friends took out colorful necklaces made by stringing together multicolored beads. The necklaces glittered in the afterglow of the sunset. Looking closely, they found that many birds had already gathered around the necklaces. The birds brought Madeline and her friends to a place they had never been to before. A huge flock of birds gathered here, seemingly trying to express something to them. After Madeline observed carefully, she found that the way some birds flew seemed to form an ordered formula, while the way other birds flew formed some symbols. These symbols described a question. The question described by the birds is as follows: The formula formed by the birds consists of `(`, `)`, `^`, `&`, `|`, `0`, `1`, and lowercase letters, and it is an expression. Specifically: - `(` and `)` are parentheses. Operations inside parentheses have higher precedence. - `&`, `|`, and `^` represent the three bitwise operations AND, OR, and XOR. These three operations have **the same precedence**. - `0` and `1` are the constants `0` and `1`. - Lowercase letters represent variables. Multiple occurrences of the same lowercase letter represent **different** variables. Each variable takes a value of `0` or `1`. - The expression is defined as follows: - A variable, `0`, and `1` are all expressions. - If $T$ is an expression, then $(T)$ is an expression. - If $S$ and $T$ are expressions, then $S\&T$, $S|T$, and $S\ \hat{}\ T$ are expressions. - For example, $(1\ \hat{}\ 1\&0)$ is an expression, and its result is $0$, but $(1\&0$ is not an expression. The birds believe that an expression that can evaluate to $1$ is beautiful. Define the beauty of an expression as the number of assignments (among all $2^v$ assignments to its $v$ variables) that make the expression evaluate to $1$. The birds also believe that the harmony of an expression is the sum of the beauties of all its **contiguous subexpressions** (including itself). The birds are fickle. From time to time, they will change the character at one position, but they promise Madeline and her friends that they will not change the parentheses, and after each modification the whole string is still an expression. Can you help Madeline and her friends compute the harmony of the entire expression after each modification? The birds also said that the expression may be too harmonious, so Madeline only needs to output the harmony modulo $998244353$.

The first line contains an integer $m$, representing the number of modifications. The second line contains a string representing the initial expression. The next $m$ lines each contain an integer $a$ and a character $b$, meaning the birds change the character at position $a$ to $b$. In the input expression, each lowercase letter represents one variable. (Note that a letter may appear multiple times, but they represent **different** variables.)

Output $m$ lines. The $i$-th line contains the value after the $i$-th modification. Since the harmony may be very large, you need to output it modulo $998244353$.

Let $n$ be the number of variables and `0,1` in the expression, and let $len$ be the expression length. There are subtasks. For $5\%$ of the testdata: $n \leq 12$, $len \leq 50$, $m \leq 50$, time limit $1\text{s}$. For an additional $10\%$ of the testdata: $n \leq 150$, $len \leq 400$, $m \leq 200$. For an additional $10\%$ of the testdata: $n \leq 10^5$, $len \leq 2\times 10^5$, $m \leq 10$, with no parentheses. For an additional $10\%$ of the testdata: $n \leq 10^5$, $len \leq 2\times 10^5$, $m \leq 10^5$, with no parentheses. For the first $50\%$ of the testdata: $n \leq 10^5$, $len \leq 4\times 10^5$, $m \leq 10^5$, and the parentheses are guaranteed to be generated randomly. For $100\%$ of the testdata: $n \leq 10^5$, $len \leq 4\times 10^5$, $m \leq 10^5$, $len-2\times n \leq 2 \times 10^5$. For the last $95\%$ of the testdata, the time limit is $3\text{s}$. Translated by ChatGPT 5