글 읽기 - [공유]All Kill 테스트 케이스 공유 + 작은 힌트

(追記) (追記ここまで)

[공유]All Kill 테스트 케이스 공유 + 작은 힌트

18527번 - All Kill

kjk9704 5달 전 0

이 문제는 주차 함수(parking function)을 이용해서 공식을 유도하여 All Kill 경우의 수를 구하면 됩니다.

이 때 MOD 연산이 존재하므로 모듈러 곱셈 역원을 활용하는 것을 권장합니다.

IN
1 1
1
OUT
1
IN
1 5
3
OUT
3
IN
2 2
1
1
OUT
3
IN
2 3
2
1
OUT
4
IN
3 4
1
1
2
OUT
16
IN
3 4
2
1
1
OUT
25
IN
3 6
2
2
1
OUT
84
IN
3 6
1
2
3
OUT
20
IN
4 4
1
1
1
1
OUT
125
IN
5 10
2
1
1
1
1
OUT
73205
IN
1 10000000
1
OUT
10000000
IN
100000 100000000
1000(100000번 데이터 입력)
OUT
748824876
# 아래는 제가 제출한 소스 코드의 일부입니다.
"""
우선 아이디어 시간이 Y1, Y2, ..., Yn이라고 할 때 그 도착시간은 {1, 2, ..., t}^n 집합의 원소입니다.
즉, 전체 경우의 수는 t^n이 되고 따라서 p * t^n은 All Kill 가능한 경우의 수입니다.
여기서 All Kill 가능한 경우의 수는 (1) 모든 문제들을 다 해결하면서 (2) 각 문제의 코딩이 끊기지 않는 것이 중요합니다.
먼저 주차 함수(parking function) 문제로 변형해서 다르게 풀 생각입니다.
그런데 주차 함수의 고전적인 형태는 원형 형태이므로 원형 주차 함수로 변형합니다.
길이 t짜리 직선에 n개의 연속 블록(길이 x_i)을 "친구가 도착 시간 Y_i에 빈 슬롯부터 순서대로 차지"하는 과정을
길이 t + 1짜리 원형으로 바꾸어 생각할 수 있습니다.
"""

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

[공유]All Kill 테스트 케이스 공유 + 작은 힌트

kjk9704 5달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말