시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 52 | 29 | 26 | 56.522% |
학습지의 대명사 구몬에서는 요즘 화제인 4차 산업혁명의 물결을 따라 얼마 전 '구몬 알고리즘' 학습지를 만들겠다고 발표했다. 아이들에게 코딩 교육을 어떻게 해야 좋을지 몰라 쩔쩔매던 학부모들은 이에 크게 열광했다.
카이스트의 자랑 구사과는 구몬 알고리즘 집필진 중 한 명으로 뽑히게 되었다. 평소 4차 산업혁명이란 말을 별로 탐탁지 않아했던 구사과는 처음에는 거절했지만, 한 문제당 5만원씩 주겠다는 구몬 측의 유혹에 홀라당 넘어가 버리고 말았다. 역시 자본주의 사회에서는 돈이 최고인 법...
그래프 알고리즘 분야를 맡게 된 구사과는 다음과 같은 문제를 생각해 냈다.
'$1$부터 $N$까지의 순열 $P$에 대해, 정점이 $N$개인 그래프에서 모든 ($i$, $P_i$) 쌍에 대해 간선을 그은 무방향성 그래프를 $G(P)$라 하자. (셀프 루프, 중복 간선도 허용한다) 정점이 $N$개인 무방향성 그래프 $X$가 주어지면, $G(P)=X$인 $P$를 모두 구해라.'
구사과는 문제의 답이 되는 순열이 너무 적지도, 많지도 않았으면 한다, 즉, $G(P)=X$인 $P$가 $l$개 이상 $r$개 이하인 $X$만 문제로 내고 싶다. 구사과는 돈을 많이 벌고 싶기 때문에 기준에 맞는 문제라면 모조리 낼 것이다. 구사과는 신사임당 지폐를 몇 장 받을 수 있을까?
첫 번째 줄에 세 개의 정수 $N$, $l$, $r$이 주어진다. ($1 \le N \le 200\, 000$, $1 \le l \le r \le 10^9$)
구사과가 낼 수 있는 서로 다른 문제의 수를 $10^9+7$로 나눈 나머지를 출력한다.
3 1 2
5
4 2 3
7
4 5 7
0
High School > 경기과학고등학교 > 나는코더다 2017 송년대회 B번