10279번 - 부분 수열이 아님 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 21 | 9 | 7 | 46.667% |
문제
이번 문제에서 크기가 k인 알파벳이란, 아래와 같은 리스트에서 처음 k개의 글자를 말한다.
a, b, c, ... , z, A, B, C, ... , Z, 0, 1, ... , 9.
각각의 테스트 케이스마다 k가 주어지며, 크기가 k인 알파벳만 고려한다.
문자열 t[1..m]이 문자열 s[1..n]의 부분 수열이 되려면, t[1] = s[i1], t[2] = s[i2], ..., t[m] = t[im]을 만족하는 인덱스 1 ≤ i1 < i2 <... im ≤ n가 존재해야 한다. 예를 들어, acb는 babcaab의 부분 수열이다.
문자열 s[1..n]이 주어졌을 때, s의 부분 수열이 아닌 문자열 t[1..m] 중에서 m 값이 가장 작은 것을 찾고, 그러한 문자열의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 t ≤ 100이 주어진다. 각각의 테스트 케이스는 알파벳의 크기 k (k ∈ [1, 62])와 문자열 s[1..n] (n ∈ [1, 106])이 주어진다.
출력
각각의 테스트 케이스마다, 두 개의 정수를 출력한다. 첫 번째 정수는 가장 작은 m이고, 두 번째 정수는 가능한 문자열 t[1..m]의 개수를 109 + 7로 나눈 나머지이다.
예제 입력 1
3 2 abba 62 0123456789 3 aabbcbbcbabcbab
예제 출력 1
3 5 1 52 4 7
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2014 J번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호