접미사 배열의 개수 Batch
Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
---|---|---|---|---|---|
1000 ms | 512 MiB | 13 | 6 | 4 | 66.67% |
길이가 $N$인 문자열 중에서 문자열을 구성하는 문자의 종류가 $M$가지 이하인 것들의 접미사 배열을 구할 때, 서로 다른 접미사 배열의 개수는 몇 개인가?
입력
첫 번째 줄에 두 자연수 $N$, $M$($1 \le N, M \le 10^{6}$)이 공백으로 구분되어 주어진다.
출력
길이가 $N$인 문자열 중에서 문자열을 구성하는 문자의 종류가 $M$가지 이하인 문자열들의 접미사 배열의 종류의 개수를 $1,000,000,007$로 나눈 나머지를 출력한다.
참고
접미사 배열의 정의는 여기에서 확인할 수 있다.
두 배열 $A$와 $B$가 서로 다르다는 것은, $A[i] \ne B[i]$를 만족하는 정수 $i$가 적어도 하나 존재한다는 것이다.
부분문제
부분문제 | 점수 | N | M |
---|---|---|---|
1 | 10 | ≤ 103 | ≤ 103 |
2 | 36 | ≤ 106 | ≤ 106 |
입출력 예제
입력
4 2
출력
12
- [4, 3, 2, 1]: "aaaa", "baaa", "bbaa", "bbba", "bbbb"
Problem Source