시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB355593113.362%

문제

$1$부터 $V$까지 번호가 붙은 정점이 $V$개, 간선이 $E$개인 단순 연결그래프가 주어진다.

각 간선의 가중치는 시간 $t$에 따라 변화하는 이차함수 $at^2+b_it+c_i$ 꼴이다. 모든 간선에 대해 $a$는 동일하다.

이때 함수 $f(t)$를 시간 $t$에서의 최소 스패닝 트리의 가중치의 합으로 정의하자.

정수 $t_1$, $t_2$가 주어지면 $\int_{t_1}^{t_2}f(t)dt$의 값을 구하시오.

최소 스패닝 트리란, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리이다.

입력

첫 번째 줄에 정수 $V$, $E$, $a$가 공백으로 구분되어 주어진다. $(1 \le V \le 100;$ $1 \le E \le 250;$ $-1\,000 \le a \le 1\,000;$ $a \neq 0)$

다음 $E$개의 줄에 간선의 정보를 나타내는 네 정수 $X$, $Y$, $b_i$, $c_i$가 공백으로 구분되어 주어진다. $(1 \le X, Y \le V;$ $-1\,000 \le b_i, c_i \le 1\,000)$

이는 $X$번 정점과 $Y$번 정점을 잇는 간선의 가중치가 $at^2+b_it+c_i$라는 뜻이다.

다음 줄에 시간을 나타내는 정수 $t_1$과 $t_2$가 공백으로 구분되어 주어진다. $(-1\,000 \le t_1 \le t_2 \le 1\,000)$

출력

$\int_{t_1}^{t_2}f(t)dt$의 값이 정수 $m$, 양의 정수 $n$에 대하여 기약분수 $\frac{m}{n}$일 때, $m\times n^{-1}\bmod (10^9+7)$을 출력한다. $n^{-1}$은 $n$의 모듈러 곱셈에 대한 역원이다.

답이 $10^9+7$의 배수가 아닌 $n$에 대해 위와 같은 꼴로 표현됨을 증명할 수 있다.

예제 입력 1

2 1 3
2 1 1 4
-3 7

예제 출력 1

430

예제 입력 2

3 3 3
1 2 2 -3
3 1 1 6
2 3 -4 12
-1 10

예제 출력 2

800001995

노트

필요하다면 $(ab^{-1})+(cd^{-1}) \equiv (ad+bc)\times(bd)^{-1} \pmod {10^9+7}$임을 이용할 수 있다.

출처

Contest > BOJ User Contest > 미적확통컵 > 2022 제1회 미적확통컵 C번