33807번 - Minimum Spanning Arborescence 서브태스크다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB1821156057.692%

문제

$r$을 루트로 하는 arborescence $G = (V, E)$란 다음 조건을 만족하는 방향 그래프를 뜻한다.

  • 다른 모든 정점 $v$에 대해, $r$에서 $v$로 가는 경로가 정확히 하나 존재한다.

DAG(Directed Acyclic Graph)란 사이클이 없는 유향 그래프를 뜻한다. DAG의 각 간선에 가중치가 부여되었을 때, DAG 위에서의 minimum spanning arborescence 란 다음과 같다.

  • DAG위에서의 $1$을 루트로 한 arborescence이다.
  • DAG 상의 모든 정점을 포함한다.
  • 사용된 간선들의 가중치 합이 최소이다. 그런 방법이 여럿 존재한다면 모두 minimum spanning arborescence이다.

정점 $N$개, 유향 간선 $M$개로 이루어진 DAG가 주어진다. $M$개의 간선에 각각 $1$이상 $K$이하의 가중치를 붙이는 $K^M$가지의 경우에 대해, minimum spanning arborescence를 구성하는 간선의 가중치 합의 기댓값을 $998\,244\,353$으로 나눈 나머지를 구하여라. 중복 간선이 있을 수 있음에 유의하라.

입력

첫 줄에 세 정수 $N, M, K$가 주어진다.

다음 $M$개의 줄에 걸쳐 $i+1$번째 줄에 간선을 뜻하는 두 정수 $a_i, b_i$가 주어진다. 이는 $a_i$에서 $b_i$로 가는 유향 간선이 존재함을 뜻한다.

출력

기댓값을 $998\,244\,353$으로 나눈 나머지를 출력한다.

즉, 기댓값이 서로소인 두 양의 정수 $a$, $b$에 대해 기약분수 $\frac{a}{b}$의 형태로 표현될 때, $b \cdot k \equiv a \pmod{998\,244\,353}$을 만족하는 유일한 정수 $k$ ($0 \le k < 998\,244\,353$)를 출력한다.

제한

  • $1 \leq N, M, K \leq 10^5 $
  • $ N-1 \leq M $
  • 모든 $1 \le i \le N$에 대하여 $ 1 \leq a_i < b_i \leq N$
  • 기존 DAG에서 1번 정점에서 다른 모든 정점에 도달할 수 있다.

서브태스크

번호배점제한
15

$M = N-1$

211

$M \leq 10, K \leq 2$

337

$N, M, K \leq 1000$

447

추가적인 제약 조건이 없다.

예제 입력 1 

10 15 3
1 2
1 3
3 4
4 5
2 6
2 7
1 8
1 9
6 10
4 9
1 8
8 9
1 2
8 10
4 10

예제 출력 1 

110916055

예제 입력 2 

4 5 1
1 2
1 3
2 4
2 3
3 4

예제 출력 2 

3

예제 입력 3 

10 9 100
1 2
1 3
3 4
3 5
5 6
2 7
2 8
6 9
7 10

예제 출력 3 

499122631

예제 입력 4 

11 10 2
1 2
1 3
2 4
4 5
3 6
1 7
5 8
8 9
2 10
3 11

예제 출력 4 

15

예제 입력 5 

5 7 2
1 2
2 3
1 4
1 5
1 5
2 4
1 4

예제 출력 5 

623902726
W3sicHJvYmxlbV9pZCI6IjMzODA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTWluaW11bSBTcGFubmluZyBBcmJvcmVzY2VuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPiRyJFx1Yzc0NCBcdWI4ZThcdWQyYjhcdWI4NWMgXHVkNTU4XHViMjk0IGFyYm9yZXNjZW5jZSAkRyA9IChWLCBFKSRcdWI3ODAgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTAgJHYkXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJHIkXHVjNWQwXHVjMTFjICR2JFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkRBRyhEaXJlY3RlZCBBY3ljbGljIEdyYXBoKVx1Yjc4MCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YzcyMFx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiBEQUdcdWM3NTggXHVhYzAxIFx1YWMwNFx1YzEyMFx1YzVkMCBcdWFjMDBcdWM5MTFcdWNlNThcdWFjMDAgXHViZDgwXHVjNWVjXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgREFHIFx1YzcwNFx1YzVkMFx1YzExY1x1Yzc1OCBtaW5pbXVtIHNwYW5uaW5nIGFyYm9yZXNjZW5jZSBcdWI3ODAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuXHJcbjx1bD5cclxuXHQ8bGk+REFHXHVjNzA0XHVjNWQwXHVjMTFjXHVjNzU4IDxzcGFuIHN0eWxlPVwiY29sb3I6I2MwMzkyYjtcIj48c3Ryb25nPiQxJDxcL3N0cm9uZz48XC9zcGFuPlx1Yzc0NCBcdWI4ZThcdWQyYjhcdWI4NWMgXHVkNTVjIGFyYm9yZXNjZW5jZVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+REFHIFx1YzBjMVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMGFjXHVjNmE5XHViNDFjIFx1YWMwNFx1YzEyMFx1YjRlNFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVhZGY4XHViN2YwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZmYgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YmFhOFx1YjQ1MCBtaW5pbXVtIHNwYW5uaW5nIGFyYm9yZXNjZW5jZVx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4MTVcdWM4MTAgJE4kXHVhYzFjLCBcdWM3MjBcdWQ1YTUgXHVhYzA0XHVjMTIwICRNJFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgREFHXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJE0kXHVhYzFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1YzVkMCBcdWFjMDFcdWFjMDEgJDEkXHVjNzc0XHVjMGMxICRLJFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHViZDk5XHVjNzc0XHViMjk0ICRLXk0kXHVhYzAwXHVjOWMwXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWIzMDBcdWQ1NzQsIG1pbmltdW0gc3Bhbm5pbmcgYXJib3Jlc2NlbmNlXHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4IFx1ZDU2OVx1Yzc1OCBcdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgJDk5OFxcLDI0NFxcLDM1MyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuIFx1YzkxMVx1YmNmNSBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3NGNcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4ICROLCBNLCBLJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCAkaSsxJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjczYlx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4ICRhX2ksIGJfaSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgJGFfaSRcdWM1ZDBcdWMxMWMgJGJfaSRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YzcyMFx1ZDVhNSBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgJDk5OFxcLDI0NFxcLDM1MyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVhZTMwXHViMzEzXHVhYzEyXHVjNzc0IFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3OCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkYSQsICRiJFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4ICRcXGZyYWN7YX17Yn0kXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHViNTRjLCAkYiBcXGNkb3QgayBcXGVxdWl2IGEgXFxwbW9kezk5OFxcLDI0NFxcLDM1M30kXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVjODE1XHVjMjE4ICRrJCAoJDAgXFxsZSBrICZsdDsgOTk4XFwsMjQ0XFwsMzUzJClcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSBOLCBNLCBLIFxcbGVxIDEwXjUgJDxcL2xpPlxyXG5cdDxsaT4kIE4tMSBcXGxlcSBNICQ8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwICQxIFxcbGUgaSBcXGxlIE4kXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyAkIDEgXFxsZXEgYV9pICZsdDsgYl9pIFxcbGVxIE4kPFwvbGk+XHJcblx0PGxpPlx1YWUzMFx1Yzg3NCBEQUdcdWM1ZDBcdWMxMWMgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRNID0gTi0xJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE0gXFxsZXEgMTAsIEsgXFxsZXEgMiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROLCBNLCBLIFxcbGVxIDEwMDAkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzM4MDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNaW5pbXVtIFNwYW5uaW5nIEFyYm9yZXNjZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+QW4gYXJib3Jlc2NlbmNlICRHID0gKFYsIEUpJCByb290ZWQgYXQgJHIkIGlzIGEgZGlyZWN0ZWQgZ3JhcGggdGhhdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBjb25kaXRpb246PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Rm9yIGV2ZXJ5IG90aGVyIHZlcnRleCAkdiQsIHRoZXJlIGV4aXN0cyBleGFjdGx5IG9uZSBkaXJlY3RlZCBwYXRoIGZyb20gJHIkIHRvICR2JC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIERBRyAoRGlyZWN0ZWQgQWN5Y2xpYyBHcmFwaCkgaXMgYSBkaXJlY3RlZCBncmFwaCB3aXRoIG5vIGN5Y2xlcy4gV2hlbiBlYWNoIGVkZ2UgaW4gdGhlIERBRyBpcyBhc3NpZ25lZCBhIHdlaWdodCwgYSBtaW5pbXVtIHNwYW5uaW5nIGFyYm9yZXNjZW5jZTxiPiA8XC9iPmlzIGRlZmluZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JdCBpcyBhbiBhcmJvcmVzY2VuY2Ugcm9vdGVkIGF0IHZlcnRleCA8c3BhbiBzdHlsZT1cImNvbG9yOiNjMDM5MmI7XCI+PHN0cm9uZz4kMSQ8XC9zdHJvbmc+PFwvc3Bhbj4uPFwvbGk+XHJcblx0PGxpPkl0IHNwYW5zIGFsbCB2ZXJ0aWNlcyBpbiB0aGUgREFHLjxcL2xpPlxyXG5cdDxsaT5BbW9uZyBhbGwgc3VjaCBhcmJvcmVzY2VuY2VzLCB0aGUgc3VtIG9mIHRoZSB3ZWlnaHRzIG9mIHRoZSBlZGdlcyB1c2VkIGlzIG1pbmltaXplZC4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHN1Y2ggYXJib3Jlc2NlbmNlcywgYWxsIG9mIHRoZW0gYXJlIGNvbnNpZGVyZWQgbWluaW11bSBzcGFubmluZyBhcmJvcmVzY2VuY2VzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBEQUcgd2l0aCAkTiQgdmVydGljZXMgYW5kICRNJCBkaXJlY3RlZCBlZGdlcy4gRWFjaCBvZiB0aGUgJE0kIGVkZ2VzIGNhbiBiZSBhc3NpZ25lZCBhIHdlaWdodCBiZXR3ZWVuICQxJCBhbmQgJEskLCByZXN1bHRpbmcgaW4gJEteTSQgcG9zc2libGUgYXNzaWdubWVudHMuIEZvciBlYWNoIHBvc3NpYmxlIGFzc2lnbm1lbnQgb2Ygd2VpZ2h0cywgY29uc2lkZXIgdGhlIG1pbmltdW0gc3Bhbm5pbmcgYXJib3Jlc2NlbmNlIHJvb3RlZCBhdCB2ZXJ0ZXggJDEkLiBDb21wdXRlIHRoZSBleHBlY3RlZCB0b3RhbCB3ZWlnaHQgb2YgdGhlIGVkZ2VzIHVzZWQgaW4gc3VjaCBhcmJvcmVzY2VuY2VzLCBhbmQgb3V0cHV0IHRoZSByZXN1bHQgbW9kdWxvICQ5OThcXCwyNDRcXCwzNTMkLiBOb3RlIHRoYXQgbXVsdGlwbGUgZWRnZXMgYmV0d2VlbiB0aGUgc2FtZSBwYWlyIG9mIHZlcnRpY2VzIG1heSBleGlzdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzICROJCwgJE0kLCBhbmQgJEskLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJE0kIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkYV9pJCBhbmQgJGJfaSQgaW5kaWNhdGluZyBhIGRpcmVjdGVkIGVkZ2UmbmJzcDtmcm9tIHZlcnRleCAkYV9pJCB0byB2ZXJ0ZXggJGJfaSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBleHBlY3RlZCB2YWx1ZSBtb2R1bG8gJDk5OFxcLDI0NFxcLDM1MyQuPFwvcD5cclxuXHJcbjxwPlRoYXQgaXMsIGlmIHRoZSBleHBlY3RlZCB2YWx1ZSBjYW4gYmUgZXhwcmVzc2VkIGFzIGEgcmVkdWNlZCBmcmFjdGlvbiAkXFxmcmFje2F9e2J9JCBmb3IgdHdvIHBvc2l0aXZlIGNvcHJpbWUgaW50ZWdlcnMgJGEkIGFuZCAkYiQsIG91dHB1dCB0aGUgdW5pcXVlIGludGVnZXIgJGskIHN1Y2ggdGhhdCAkMCBcXGxlIGsgJmx0OyA5OThcXCwyNDRcXCwzNTMkIGFuZCAkYiBcXGNkb3QgayBcXGVxdWl2IGEgXFxwbW9kezk5OFxcLDI0NFxcLDM1M30kLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZXEgTiwgTSwgSyBcXGxlcSAxMF41ICQ8XC9saT5cclxuXHQ8bGk+JCBOLTEgXFxsZXEgTSAkPFwvbGk+XHJcblx0PGxpPiQgMSBcXGxlcSBhX2kgJmx0OyBiX2kgXFxsZXEgTiQgZm9yIGV2ZXJ5Jm5ic3A7ICQxIFxcbGUgaSBcXGxlIE4kPFwvbGk+XHJcblx0PGxpPkluIHRoZSBnaXZlbiBEQUcsIHZlcnRleCAkMSQgY2FuIHJlYWNoIGV2ZXJ5IG90aGVyIHZlcnRleC48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JE0gPSBOIC0gMSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRNIFxcbGUgMTAkLCAkSyBcXGxlIDIkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiwgTSwgSyBcXGxlIDEsMDAwJDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4ifV0=

출처

University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest E번

채점 및 기타 정보

  • 예제는 채점하지 않는다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)