팰린드롬 부분 문자열

시간 제한2초메모리 제한512 MB

요약

길이 N의 대문자 문자열 중 길이 M인 부분 문자열 가운데 회문이 K개 이상인 문자열의 수를 센다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 문자열, 재귀, 비트 연산
정답자: 아직 제출이 없습니다

문제

알파벳 대문자로만 이루어진 길이 $N$ 의 문자열을 생각하자. 이런 문자열에는 길이가 $M$ 인 부분 문자열이 시작 위치마다 하나씩, 모두 $N-M+1$ 개 있다. 이 가운데 팰린드롬인 것이 $K$ 개 이상인 문자열의 개수를 구하는 프로그램을 작성하시오. 내용이 같은 부분 문자열이 서로 다른 위치에서 시작하면 각각 따로 센다.

입력

첫째 줄에 $N$ , $M$ , $K$ 가 공백으로 구분되어 주어진다. ( $2 \le M \le N \le 11$ , $0 \le K \le 11$ )

출력

첫째 줄에 조건을 만족하는 문자열의 개수를 출력한다. 정답은 $2^{63}-1$ 보다 작거나 같다.

힌트

$N=2$ , $M=2$ , $K=1$ 이면 AA, BB, CC부터 ZZ까지 두 글자가 같은 문자열만 조건을 만족한다. $K=0$ 이면 팰린드롬이 하나도 없어도 되므로 길이가 $N$ 인 문자열 전부가 조건을 만족한다.

예제5

예제 1
입력
```
2 2 1
```
예상 출력
```
26
```
예제 2
입력
```
2 2 0
```
예상 출력
```
676
```
예제 3
입력
```
3 2 1
```
예상 출력
```
1326
```
예제 4
입력
```
4 4 1
```
예상 출력
```
676
```
예제 5
입력
```
7 3 3
```
예상 출력
```
4310176
```