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）是她最大的樂趣之一。

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

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

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

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

Input Format

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

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

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

  • 1≤N≤50000
  • 0≤Q≤50000
  • 0≤A,B,C<998244353
  • 1≤p≤N
  • |S|=N
  • Si,x∈{A, C, ?}

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=A??C，以下為所有可能的問題與分別所需花費的精力：

  • AAAC 最少需要 3 次修改，所需的精力為 2⋅3+3=9
  • AACC 最少需要 4 次修改，所需的精力為 2⋅4+3=11
  • ACAC 最少需要 3 次修改，所需的精力為 2⋅3+3=9
  • ACCC 最少需要 3 次修改，所需的精力為 2⋅3+3=9

因此需輸出 38。

在第一次修改後，S=AC?C。

在第二次修改後，S=CC?C。

在第三次修改後，S=?C?C。

在第四次修改後，S=?C??。

在第五次修改後，S=?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