131 . 滅台題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

90.9% (10/11)

Tags

ioicamp ioicamp-2023

Description

伊烏是個強大的出題者，她喜歡在比賽中出一些困難的題目來難倒參賽選手們，像是難難倍增問題、怪怪背包問題以及酷酷圓規問題等都是她的代表作。看著參賽選手們絞盡腦汁依然沒有辦法在這題拿到 AC（Accepted）是她最大的樂趣之一。

為了能夠產出品質優秀的難題，當伊烏有題目的靈感後，她會用獨特的方式慢慢改變這道題目，最後變成困難的滅台題。

具體來說，她會先將題目用一個僅由 $\texttt{A}$, $\texttt{C}$ 組成且長度 $N$ 的字串來表示，接著她有 $N - 1$ 種修改題目的方式，第 $i$ 種修改方式會讓字串的第 $i$ 個字元與第 $i + 1$ 個字元交換，在經過數次的修改後，如果字串沒有 $\texttt{AC}$ 作為子字串（意即：不存在一個位置 $i$ 使得第 $i$ 項為 $\texttt{A}$ 且第 $i + 1$ 項為 $\texttt{C}$）的話就完成一道難題了！

然而修改一次題目是需要花很大精力的，當修改次數越多，所需要的精力也會隨之增加。具體來說，假設需要對一道題目修改 $x$ 次，則伊烏需要花費的精力為 $Ax^ 2 + Bx + C$，其中 $A, B, C$ 皆為給定的非負整數。

今天伊烏又發明了一道題目，然而由於題目還不完整，表示的字串有些字元會是 $\texttt{?}$，代表該字元可能是 $\texttt{A}$ 或 $\texttt{C}$。為了減少負擔，伊烏想要知道，若一一計算所有可能的題目要變成難題所需要花的最小精力，則所有的精力總和為多少？同時，她會對題目進行 $Q$ 次修改，每次會將表示的字串某一個字元進行修改。身為伊烏的助手，請在一開始以及每次修改後都回答一次伊烏的問題。由於答案可能很大，請將答案模 $998244353$ 後輸出。

Input Format

輸入第一行有五個整數 $N, Q, A, B, C$，變數的意義與題目相同。

第二行有一個長度為 $N$ 的字串 $S$，代表一開始表示題目的字串。

接下來有 $Q$ 行，每行會包含一個整數 $p$ 以及一個字元 $x$，代表伊烏修改題目會將字串的第 $p$ 個字元變成 $x$。

  • $1 \leq N \leq 50000$
  • $0 \leq Q \leq 50000$
  • $0 \leq A, B, C < 998244353$
  • $1 \leq p \leq N$
  • $|S| = N$
  • $S_i, x \in \lbrace\texttt{A}$, $\texttt{C}$, $\texttt{?}\rbrace$

Output Format

請輸出 $Q + 1$ 行，每行都有一個整數，其中第一行為一開始的答案，接下來 $Q$ 行中的第 $i$ 行為第 $i$ 次修改後的答案。

Sample Input 1

4 5 0 2 3
A??C
2 C
1 C
1 ?
4 ?
2 A

Sample Output 1

38
18
8
26
44
52

Sample Input 2

4 5 1 2 3
A??C
2 C
1 C
1 ?
4 ?
2 A

Sample Output 2

81
36
9
45
68
90

Hints

在第一筆範測中，一開始 $S = \texttt{A??C}$，以下為所有可能的問題與分別所需花費的精力：

  • $\texttt{AAAC}$ 最少需要 $3$ 次修改，所需的精力為 $2 \cdot 3 + 3 = 9$
  • $\texttt{AACC}$ 最少需要 $4$ 次修改，所需的精力為 $2 \cdot 4 + 3 = 11$
  • $\texttt{ACAC}$ 最少需要 $3$ 次修改，所需的精力為 $2 \cdot 3 + 3 = 9$
  • $\texttt{ACCC}$ 最少需要 $3$ 次修改，所需的精力為 $2 \cdot 3 + 3 = 9$

因此需輸出 $38$。

在第一次修改後，$S = \texttt{AC?C}$。

在第二次修改後，$S = \texttt{CC?C}$。

在第三次修改後，$S = \texttt{?C?C}$。

在第四次修改後，$S = \texttt{?C??}$。

在第五次修改後，$S = \texttt{?A??}$。

Problem Source

IOICamp 2023 Day5 pF

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~20 $A = 0, Q = 0$ 20
3 0, 2~38 $A = 0$ 30
4 0~56 無其他限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 3 4
1 3000 524288 65536 1 4
2 3000 524288 65536 2 3 4
3 3000 524288 65536 2 3 4
4 3000 524288 65536 2 3 4
5 3000 524288 65536 2 3 4
6 3000 524288 65536 2 3 4
7 3000 524288 65536 2 3 4
8 3000 524288 65536 2 3 4
9 3000 524288 65536 2 3 4
10 3000 524288 65536 2 3 4
11 3000 524288 65536 2 3 4
12 3000 524288 65536 2 3 4
13 3000 524288 65536 2 3 4
14 3000 524288 65536 2 3 4
15 3000 524288 65536 2 3 4
16 3000 524288 65536 2 3 4
17 3000 524288 65536 2 3 4
18 3000 524288 65536 2 3 4
19 3000 524288 65536 2 3 4
20 3000 524288 65536 2 3 4
21 3000 524288 65536 3 4
22 3000 524288 65536 3 4
23 3000 524288 65536 3 4
24 3000 524288 65536 3 4
25 3000 524288 65536 3 4
26 3000 524288 65536 3 4
27 3000 524288 65536 3 4
28 3000 524288 65536 3 4
29 3000 524288 65536 3 4
30 3000 524288 65536 3 4
31 3000 524288 65536 3 4
32 3000 524288 65536 3 4
33 3000 524288 65536 3 4
34 3000 524288 65536 3 4
35 3000 524288 65536 3 4
36 3000 524288 65536 3 4
37 3000 524288 65536 3 4
38 3000 524288 65536 3 4
39 3000 524288 65536 4
40 3000 524288 65536 4
41 3000 524288 65536 4
42 3000 524288 65536 4
43 3000 524288 65536 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4
51 3000 524288 65536 4
52 3000 524288 65536 4
53 3000 524288 65536 4
54 3000 524288 65536 4
55 3000 524288 65536 4
56 3000 524288 65536 4
Submit
Back to Top