USACO 2018-2019 US Open Contest ? Platinum- 개미 > 문제은행 : 정보올림피아드&알고리즘




3369 : 개미

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
1 회   
시도횟수
10 회   

문제

정올아파트 놀이터 구석엔 n*m의 격자 형태의 개미집이 있다. 

개미집의 구조는 n*m개의 방이 각각 격자 위에 놓여있고, 가로, 세로로 인접한 방 사이에는 서로 이동할 수 있는 개미 통로가 있다. 

개미들은 낮에는 열심히 이 통로를 통해 일하다가, 밤에는 한 방에 한 마리씩 들어가서 잠을 잔다. 

상수 개미는 다른 개미들이 열심히 일할 때, 혼자 자기 방에서 프로그래밍 공부를 하는 개미이다. 

그 때문에 개미 동료들은 상수 개미를 1인분도 못하는 개미라고 멸시한다.

 

어느 날 밤, 못된 택쌤이 상수 개미의 집을 밟아버렸다. 

개미들의 방은 튼튼하기 때문에 개미들은 다치지 않았지만, 모든 개미 통로가 무너져버렸다. 

그래서 각 방에 한 마리씩의 개미가 고립되어 버렸다. 

개미들은 새로운 통로를 파서 모든 개미 방이 연결되도록 하고자 한다. 

그런데 통로가 될 수 있는 위치들마다 지반이 다르기 때문에, 한 통로를 뚫는데 드는 비용도 각각 다르다.

 

다행히 상수 개미가 남들이 일하는 동안 미리 분석해놓은 데이터가 있기 때문에, 걱정할 필요가 없다. 

상수 개미가 새로 개발한 앱 하나면, 최소비용으로 개미집을 짓는 방법을 찾는 것은 간단하다. 

그러나 언제 못된 택쌤이 또 개미들을 괴롭히러 올지 모르기 때문에, 

상수 개미는 이에 한 술 더 떠서, 최소비용으로 개미집을 짓는 모든 방법의 수를 찾으려고 한다.

 

상수 개미를 도와, 최소 비용으로 개미집을 짓는 모든 경우의 수를 찾는 프로그램을 작성하라. 

답이 클 수가 있기 때문에, 10^9+7로 나눈 나머지를 구하여라.​ 

 


입력형식

첫 줄에 n과 m이 공백을 사이에 두고 주어진다. 다음 n 줄에 걸쳐서, m-1개의 가로 방향 통로의 재건 비용이 주어진다. a번째 줄 b번째 수의 의미는 (a,b)에서 (a,b+1)를 잇는 통로의 비용이다. 그 다음 m 줄에 걸쳐서 n-1개의 세로 방향 통로의 재건 비용이 주어진다. c번째 줄, d번째 수의 의미는 (d,c)에서 (d+1,c)를 잇는 통로의 비용이다. 부분문제의 제약 조건 모든 부분문제에서 2<=n<=30,000, 2<=m<=6을 만족한다. 모든 비용은 1이상 10^9이하이며, 모든 입력은 정수로 주어진다. 부분문제 1: 전체 점수 100점 중 20점에 해당하며, n<=500이다. 부분문제 2: 전체 점수 100점 중 20점에 해당하며, n<=5,000이다 부분문제 3: 전체 점수 100점 중 60점에 해당하며, 주어진 조건 외의 아무런 제약조건이 없다.

출력형식

첫 줄에, 최소 비용으로 개미집을 재건하는 모든 경우의 수를 10^9+7로 나눈 나머지를 출력한다.

입력 예

4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1

출력 예

10

Hint!

주어진 입력 예시는 다음과 같다. 각 방은 +로 나타나 있다. 최소비용으로 모든 방을 연결하는 방법은, 비용 2짜리와 3짜리 통로를 연결하고 9개의 비용 1짜리 통로를 연결하는 것이다. 비용 1짜리 통로로 가능한 곳이 10군데 있으므로, 모든 경우의 수는 안 쓰는 통로 하나를 고르는 경우의 수인 10이 된다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP