25334번 - 긴 케이크 나눠주기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (하단 참고) | 512 MB | 113 | 48 | 33 | 50.769% |
문제
Albert는 길이가 $n$인 길다란 케이크를 구웠다. 이 케익은 $n$등분 할 수 있도록 총 $n$개의 칸으로 미리 나눠져있고, 일부 칸에는 과일 토핑이 올려져있다.
예를 들어 아래 그림은 $n = 8$인 케이크이고 $0$은 토핑이 없는 칸, $1$은 과일 토핑이 있는 칸을 나타낸다. 이를 정수 배열로 나타내면 $A = [0, 1, 1, 0, 0, 1, 1, 0]$로 표현할 수 있다. 구체적으로, $A[i]$는 $i$번째 칸에 토핑이 있으면 $1$, 없으면 $0$이다.
Albert는 이 케이크를 정확히 $k-1$번 잘라 $k$개의 조각으로 나누고 싶은데, 아래 조건을 만족하도록 자르고 싶다:
- 조건 1: 각 케이크 조각에 포함된 토핑이 올라간 칸의 개수가 모두 동일해야한다.
- 조건 2: 버려지는 칸이나 조각이 생겨서는 안된다.
예를 들어 $k = 2$ 인 경우 버려지는 칸이나 조각 없이 위 케이크를 자를 수 있는 방법은 총 $7$가지 존재한다. 그 중 조건 1을 만족하는 경우는 아래와 같이 세 가지 방법이다. 각 케이크 조각에는 토핑이 올라간 칸이 두 개씩 있다.
다른 예로, 아래 그림은 $n = 5$, $A = [0, 1, 0, 1, 0]$, $k = 2$인 경우 위 조건들을 만족하면서 케이크를 자를 수 있는 두 가지 방법을 나타낸다.
입력으로 $n$, $k$, 그리고 토핑의 유무를 나타내는 배열 $A$가 주어졌을 때, 조건을 만족하며 케이크를 자를 수 있는 방법이 총 몇 가지 있는지 구해보자. 단, 답이 매우 클 수 있으므로 $10^9+7$ 로 나눈 나머지를 출력한다.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스는 두 줄에 나누어 주어진다. 첫 줄에 $n$과 $k$가 공백으로 구분되어 주어진다. 둘째 줄에 배열 $A$의 값이 주어지는데, 공백없이 길이 $n$인 문자열 형태로 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- $1 ≤ T ≤ 10$
- $1 ≤ k ≤ n ≤ 1\,000\,000$
예제 입력 1
9 1 1 1 5 1 01010 5 2 01010 5 3 01010 8 2 01100110 14 2 00100100100100 13 3 0111010100100 61 21 1001001001001001001001001001001001001001001001001001001001001 3 2 000
예제 출력 1
1 1 2 0 3 3 2 486784380 2
예제 1: 케이크 길이가 $1$이며 이를 한 조각으로 나누는 방법은 한 가지이다 (이 때 케이크는 $0$회 자른다).
예제 2: 예제 1과 마찬가지로 $k = 1$인 경우 답은 $1$이다.
예제 3: [01][010]과 [010][10]의 두 가지 방법으로 조건을 만족하며 케이크를 자를 수 있다.
예제 4: 토핑이 올라간 칸이 $2$칸이지만 $k = 3$이므로 조건 2를 만족하는 방법은 없다.
예제 5: 본문에서 다루었다.
예제 8: 조건을 만족하며 케이크를 자를 수 있는 방법의 수는 $3\,486\,784\,401$이지만 $10^9+7$ 로 나눈 나머지를 출력해야 함에 유의하자.
예제 9: 케이크 위에 토핑이 하나도 없을 수도 있다.
시간 제한
- Java 8: 3 초
- Python 3: 5 초
- PyPy3: 5 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호