앳코더90 - 015 - Don't be too close（★6）

https://atcoder.jp/contests/typical90/tasks/typical90_o

015 - Don't be too close（★6）

 

문제를 사실 못풀었다. editorial도 못찾아서 다른 사람 코드를 참고했는데 조합론, 수학문제 같아서 이해하기를 포기했다.

1부터 N까지의 정수가 적힌 N개의 공이 있을때, 다음 조건을 만족하는 선택 방법을 구하여라. 선택한 어떤 두개의 공에 대해서 적힌 정수의 차이가 k이상인 경우의 수를 10^9+7로 나눈 나머지로 출력하라. k는 1~N까지 각각에 대해 시행한다.

 

N = 2인 경우에

k = 1일 때, {1}, {2}, {1,2} 이렇게 뽑을 수 있어서 3

k = 2 일때, {1}, {2} 이렇게 뽑을 수 있어서 2 이다.

 

별표가 많은 이유는 조합론과 분할거듭제곱의 테크닉이 들어간 문제라서 그런것 같다.

수학이라 잘 모르겠어서 언젠가 돌아오도록 하자.