5회 문제풀이 03 / ABC 211 C - chokudai
ABC 211 C - chokudai
【문제 개요】
문자열 S가 주어집니다. 이 중 8문자를 선택해 밑줄을 긋고, 밑줄을 그은 문자가 왼쪽부터 순서대로 c,h,o,k,u,d,a,i가 되도록 하는 방법은 몇 가지 있습니까?
단, 답변이 엄청나게 커질 가능성이 있기때문에 (10⁹ + 7)으로 나눈 나머지를 출력하시오.
힌트 : 동적 프로그래밍(DP)
【전제】
- S는 영소문자로 구성되어있다.
- 1 ≤ S의 길이 ≤ 10⁵
【입력 형태】
1
S
【출력 형태】
(10⁹ + 7)로 나눈 나머지를 출력하라.
【예시】
입력 예 1
1
chchokudai
출력 예 1
1
3
- ch ch okudai
- c hc hokudai
- ch chokudai 위와 같은 3가지 방법이 조건을 충족합니다. c hc h okudai 는 순서가 일치하지 않기때문에 조건을 만족하지 않습니다.
입력 예 2
1
atcoderrr
출력 예 2
1
0
답변으로 0이 출력될 수도 있습니다.
입력 예 3
1
chokudaichokudaichokudai
출력 예 3
1
45
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。