31544번 - K의 배수 Extreme 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 111 | 60 | 44 | 53.012% |
문제
준혁이는 $1$부터 $N$까지의 수가 적힌 공을 각각 $M$개씩 가지고 있다. 그리고 같은 숫자가 적힌 $M$개의 공들은 모두 색이 다르다. 준혁이는 $N$의 약수 중 $K$를 하나 정하고 자신이 가진 $N\times M$개의 공들 중 한 개 이상의 공을 뽑아 적힌 수의 합이 $K$의 배수가 되도록 하는 경우의 수를 구하고자 한다.
준혁이가 뽑은 공들 중 하나라도 색깔 혹은 적힌 수가 다르면 다른 경우로 센다.
입력
첫 번째 줄에 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1\le N, M, K\le 10^6)$
출력
준혁이가 공들에 적힌 수들의 합이 $K$의 배수가 되도록 한 개 이상의 공을 뽑는 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.
단, $10^9+7$은 소수이다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 26 | $K=1$ |
| 2 | 74 | $K \le 2$ |
| 3 | 28 | $N \times M \le 20$ |
| 4 | 82 | $N, M \le 300$ |
| 5 | 190 | 추가적인 제한 조건 없음 |
예제 입력 1
4 1 1
예제 출력 1
15
편의상 $1$부터 $4$까지 적힌 빨간색 공이 한 개씩 있다고 하자. 이 중 한 개 이상의 공을 뽑아 $1$의 배수가 되는 경우는 다음과 같이 $4+4+2+2+2+1=15$가지이다.
- 합이 $1$, $2$, $3$인 경우 $4$가지
- 합이 $4$, $5$인 경우 $4$가지
- 합이 $6$인 경우 $2$가지
- 합이 $7$인 경우 $2$가지
- 합이 $8$, $9$인 경우 $2$가지
- 합이 $10$인 경우 $1$가지
���제 입력 2
4 1 2
예제 출력 2
7
편의상 $1$부터 $4$까지 적힌 빨간색 공이 한 개 씩 있다고 하자. 이 중 한 개 이상의 공을 뽑아 $2$의 배수가 되는 경우는 다음과 같이 $3+2+2=7$가지이다.
- 합이 $2$, $4$인 경우 $3$가지
- 합이 $6$인 경우 $2$가지
- 합이 $8$, $10$인 경우 $2$가지
예제 입력 3
3 2 3
예제 출력 3
23
편의상 $1$부터 $3$까지 적힌 빨간색, 파란색 공이 각각 한 개씩 있다고 하자. 이 중 한 개 이상의 공을 뽑아 $3$의 배수가 되는 경우는 다음과 같이 $6+10+6+1=23$가지이다.
- 합이 $3$인 경우 $6$가지
- 합이 $6$인 경우 $10$가지
- 합이 $9$인 경우 $6$가지
- 합이 $12$인 경우 $1$가지
예제 입력 4
4 5 4
예제 출력 4
262143
예제 입력 5
33 1 3
예제 출력 5
863312881
예제 입력 6
780885 280188 780885
예제 출력 6
457247866
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring L번
- 문제를 만든 사람: alex04, kidw0124, leeminjae
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: coo001, finimage, kevinlys00, sshs29hanul, tlsdydaud1, utilforever, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호