| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 828 | 218 | 184 | 29.535% |
그래프의 변환$(f:G \mapsto G')$을 다음과 같이 정의한다. $G$의 간선을 $G'$의 정점으로 보고 $G$의 인접한 간선끼리 $G'$에서 간선으로 연결하여 $G$에서 인접하였음을 나타낸다.
서로 다른 두 간선이 같은 정점을 하나 이상 공유하면 두 간선이 인접한다고 표현한다.
다음은 그래프 변환의 예시 중 하나이다.
그리고 변환한 그래프를 다시 변환하는 것도 가능하다.
$N$-완전 그래프를 $K$번 변환한 그래프의 정점이 몇 개인지 구하시오. $N$-완전 그래프는 정점이 $N$개인 그래프에서 서로 다른 두 정점에 대해 반드시 간선이 존재하는 그래프이다.
첫째 줄에 정수 $N$, $K$가 공백을 사이에 두고 주어진다. $(3 \leq N \leq 100 \, 000;$ $\, 0 \leq K \leq 100 \, 000)$
$K$번 변환한 그래프의 정점의 개수를 $1 \, 000 \, 000 \, 007(= 10^9 + 7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.
4 1
6
$4$-완전 그래프를 $1$번 변환한 그래프의 정점의 개수는 그림과 같이 $6$개이다.
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 12. D번