rb3krn   3년 전

문제

 Gunilla는 자신이 즐겨찾는 웹사이트로 이동하고자 합니다. 그러나 가끔 주소의 특정 글자를 잘못 쳐 다른 사이트로 이동하기도 합니다. 이때 흥미로운 점은 동일한 실수는 두 번 이상 하지 않는다는 것입니다.

 해커는 그녀를 자신의 사이트로 유인하기 위해 가능한 모든 경우의 주소를 등록하려고 합니다. 그녀가 접속하려는 사이트 주소, 그리고 어떤 글자를 헷갈려하는 지에 대한 정보가 주어질 때, 해커가 등록해야 하는 주소의 개수를 구하세요.

입력

  • 첫번째 줄에 접속하려는 사이트의 주소인 문자열이 주어집니다. 알파벳 소문자와 콤마로만 이루어져 있으며, 반드시 실제 주소이거나 주소 형식을 따르는 것은 아닙니다.
  • 두번쨰 줄에는 정수 N이 주어집니다. (1 <= N <= 13) 이는 Gunilla가 헷갈려하는 글자 그룹의 개수입니다. 이하 N개의 줄에서는 한 줄씩 2 이상 26 이하 길이의 문자열이 주어집니다. 각 문자열은 서로 다른 알파벳 소문자들로 구성되어 있으며, 문자열의 각 문자들은 서로 바뀔 수 있는 하나의 그룹을 형성합니다. 예를 들어 "boi"라는 문자열은 'b'가 'o' 또는 'i'로, 'o'가 'b' 또는 'i'로 오타 날 수 있음을 의미합니다.
  • 문자는 여러 그룹에 중복되어 나타나지 않습니다.

출력

한 번 이상의 오타에 의하여 나올 수 있는 모든 주소의 개수. 단, 같은 실수(특정 글자 x가 특정 글자 y로 바뀜)가 여러 번 나오는 경우는 제외합니다.

제한

문제의 답은 20억을 초과하지 않습니다.

힌트

예제 1, 2, 3에서 가능한 모든 주소는 다음과 같습니다.

(본문 참고)

이때 같은 실수를 두번 한 "karris.com" 이나 "ebbe" 같은 경우는 포함되지 않음에 유의하십시오.

댓글을 작성하려면 로그인해야 합니다.