¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8192
Subtarea

별명 짓기 2s 1024MB

Problemas

당신은 쌍둥이 친구 두 명을 만났다. 형의 이름은 A이며, N개의 문자로 이루어져 있다. 동생의 이름은 B이며, M개의 문자로 이루어져 있다. 이때, N ≤ M이 성립한다. 당신은 두 사람에게 각각 별명을 지어주고 싶다. 형의 별명은 A의 임의의 순열 중 하나를 선택하여 A'로 정한다. 동생의 별명은 B의 임의의 순열에서 정확히 M - N개의 문자를 제거한 결과 중 하나를 선택하여 B'로 정한다. 또한 1 ≤ i ≤ N을 만족하는 모든 i에 대해, B'_i는 반드시 다음 중 하나를 만족해야 한다.

  • A'_i와 같다.

  • A'_i의 로마자 상 바로 다음 문자와 같다 (만약 다음 문자가 존재할 경우).

이 조건을 만족하는 서로 다른 별명 쌍 (A', B')의 개수를 구하라. 두 별명 쌍이 다르다는 것은 적어도 하나의 별명이 다르다는 것을 의미한다. 결과가 클 수 있으므로 998\,244\,353로 나눈 나머지를 출력하라.


Entrada

첫 번째 줄에 두 정수 N, M이 주어진다 (1 ≤ N ≤ M ≤ 200\,000).
두 번째 줄에 길이가 N인 문자열 A가 주어진다.
세 번째 줄에 길이가 M인 문자열 B가 주어진다.
문자열은 모두 로마자 대문자로만 구성되어 있다.


Salida

조건을 만족하는 별명 쌍 (A', B')의 개수를 998\,244\,353로 나눈 나머지를 출력한다.


Subtarea

# Puntaje Condición
#15

N ≤ M ≤ 6

#25

주어지는 모든 문자는 로마자 Y 또는 Z이다.

#330

N ≤ M ≤ 2000

#460

추가 제한 조건이 없다.


Ejemplo #1

3 4
AMA
ANAB
9

가능한 9개의 쌍은 다음과 같다.

  • (AAM, AAN)

  • (AAM, ABN)

  • (AAM, BAN)

  • (AMA, ANA)

  • (AMA, ANB)

  • (AMA, BNA)

  • (MAA, NAA)

  • (MAA, NAB)

  • (MAA, NBA)


Ejemplo #2

5 8
BINUS
BINANUSA
120

Ejemplo #3

15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA
151362308

Ejemplo #4

4 4
UDIN
ASEP
0

Fuente

The 2023 ICPC Asia Jakarta Regional Contest

Debes iniciar sesión para escribir código.