r969. PF. Twin Friends - 高中生程式解題系統

內容

你結識了兩位新朋友，她們是雙胞胎。姊姊的名字是 A ，由 N 個字元組成。妹妹的名字是 B ，由 M 個字元組成。已知 N ≤ M 。

你想給他們每個人取一個暱稱。對於姊姊，你想從 A 的任意排列中選取一個暱稱。對於妹妹，你想要從 B 的任意排列中移除 M - N 個字元。將姊姊和妹妹的暱稱分別記為 A' 和 B' .

您希望暱稱滿足以下要求。對於滿足 1 ≤ i ≤ N 的每個 i， B'_i 必須等於 A'_i 或 A'_i 之後按字母順序排列的下一個字母（如果存在這樣的下一個字母）。

確定滿足要求的不同暱稱對 (A' , B' ) 的數量。如果兩個暱稱對中至少有一個不同，則認為它們是不同的。由於結果可能很大，因此求答案對 998244353 取模。

輸入說明

第一行由兩個整數 N M ( 1 ≤ N ≤ M ≤ 200000 )組成。

第二行由長度為 N 的字串 A 組成。

第三行由長度為 M 的字串 B 組成。

所有字串均僅由大寫字母組成。

輸出說明

輸出一個整數，表示滿足要求的不同數對 (A' , B' ) 的數量，模 998244353 。

範例輸入 #1

3 4
AMA
ANAB

範例輸出 #1

範例輸入 #2

5 8
BINUS
BINANUSA

範例輸出 #2

範例輸入 #3

15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA

範例輸出 #3

151362308

範例輸入 #4

4 4
UDIN
ASEP

範例輸出 #4

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 0.1s , <1K
不公開測資點#1 (5%): 0.1s , <1K
不公開測資點#2 (5%): 0.1s , <1M
不公開測資點#3 (5%): 0.1s , <1M
不公開測資點#4 (5%): 0.1s , <1M
不公開測資點#5 (5%): 0.1s , <1M
不公開測資點#6 (5%): 0.1s , <1M
不公開測資點#7 (5%): 0.1s , <1M
不公開測資點#8 (5%): 0.1s , <1M
不公開測資點#9 (5%): 0.1s , <1M
不公開測資點#10 (5%): 0.1s , <1M
不公開測資點#11 (5%): 0.1s , <1M
不公開測資點#12 (5%): 0.1s , <1M
不公開測資點#13 (5%): 0.1s , <1M
不公開測資點#14 (5%): 0.1s , <1M
不公開測資點#15 (5%): 0.1s , <1M
不公開測資點#16 (5%): 0.1s , <1M
不公開測資點#17 (5%): 0.1s , <1M
不公開測資點#18 (5%): 0.1s , <1M
不公開測資點#19 (5%): 0.1s , <1M

提示：

範例一說明:

9 對是：

(AAM, AAN),
(AAM, ABN),
(AAM, BAN),
(AMA, ANA),
(AMA, ANB),
(AMA, BNA),
(MAA, NAA),
(MAA, NAB),
(MAA, NBA).

標籤:

2023 ICPC Asia Jakarta Regional Contest H DP contest Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」