(DeepL로 한국어로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
JAG대학교 ICPC학과에는 N명의 재학생이 있으며, 각 학생에게는 1부터 N까지의 학번이 부여되어 있다. 또한, 학생들 사이의 친구 관계는 M개 존재한다. i번째 친구 관계는 ai와 bi의 순서쌍으로 나타낼 수 있으며, 학생 ai와 bi가 친구이고 서로 연락을 주고받을 수 있음을 의미한다.
학과 기말고사에서는 총 N과목의 시험을 실시할 예정이다. 학생 i는 i번 과목의 족보를 가지고 있다. 당신은 학생 1이다. 친구들끼리 족보 공유를 반복할 때 몇 과목의 족보를 모을 수 있는지 궁금해진 당신은 친구들끼리 족보를 K번 공유했을 때 족보 개수의 기댓값을 구하려고 한다.
다음 연산을 순서대로 K회 독립시행한다고 하자.
M개의 친구 관계 중 하나가 무작위로 선택되어 두 학생이 연락을 주고받는다. 이때 두 학생은 각자 가지고 있는 모든 족보를 공유한다.
즉, 두 학생이 가지고 있는 족보의 집합을 각각 X와 Y라고 할 때, 시행 이후 두 학생이 가지고 있는 족보의 집합은 모두 X ∪ Y가 된다.
K회의 시행이 끝난 뒤, 학생 1인 당신이 가지고 있게 되는 족보 수의 기댓값을 모듈로 998,244,353 위에서 구하여라.
문제에서 구하는 기댓값은 항상 유리수이고, 문제의 제한 이내에서 기댓값을 P/Q로 나타낼 때 Q ≢ 0 (mod 998,244,353)임을 보일 수 있으며, 여기에서R ×Q ≡ P (mod 998,244,353), 0 ≤ R < 998,244,353을 만족하는 정수 R이 유일하게 결정된다. 이 R이 모듈로 998,244,353 위의 기댓값이다. 998,244,353 = 223 × 7 × 17 + 1은 소수이다.
입력
입력은 최대 50개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
N M K
a1 b1
...
aM bM
첫째 줄에는 학생 수 N, 친구 관계의 개수 M, 시행 횟수 K가 주어진다. (2 ≤ N ≤ 10, 1 ≤ M ≤ N(N-1)/2, 1 ≤ K ≤ 50)
둘째 줄부터 M줄에 걸쳐 친구 관계가 주어진다. 이 중 i번째 줄에는 ai와 bi가 주어진다. (1 ≤ ai, bi ≤ N) 자기 자신과 친구인 경우는 없다. 즉, 모든 1 ≤ i ≤ M에 대해 ai ≠ bi이다. 또한, 같은 친구 관계가 여러 번 주어지지 않는다. 즉, 모든 1 ≤ i, j ≤ M에 대해 i ≠ j이면 {ai, bi} ≠ {aj, bj}이다.
dlaud5379 1년 전
(DeepL로 한국어로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
JAG대학교 ICPC학과에는 N명의 재학생이 있으며, 각 학생에게는 1부터 N까지의 학번이 부여되어 있다. 또한, 학생들 사이의 친구 관계는 M개 존재한다. i번째 친구 관계는 ai와 bi의 순서쌍으로 나타낼 수 있으며, 학생 ai와 bi가 친구이고 서로 연락을 주고받을 수 있음을 의미한다.
학과 기말고사에서는 총 N과목의 시험을 실시할 예정이다. 학생 i는 i번 과목의 족보를 가지고 있다. 당신은 학생 1이다. 친구들끼리 족보 공유를 반복할 때 몇 과목의 족보를 모을 수 있는지 궁금해진 당신은 친구들끼리 족보를 K번 공유했을 때 족보 개수의 기댓값을 구하려고 한다.
다음 연산을 순서대로 K회 독립시행한다고 하자.
K회의 시행이 끝난 뒤, 학생 1인 당신이 가지고 있게 되는 족보 수의 기댓값을 모듈로 998,244,353 위에서 구하여라.
문제에서 구하는 기댓값은 항상 유리수이고, 문제의 제한 이내에서 기댓값을 P/Q로 나타낼 때 Q ≢ 0 (mod 998,244,353)임을 보일 수 있으며, 여기에서 R × Q ≡ P (mod 998,244,353), 0 ≤ R < 998,244,353을 만족하는 정수 R이 유일하게 결정된다. 이 R이 모듈로 998,244,353 위의 기댓값이다. 998,244,353 = 223 × 7 × 17 + 1은 소수이다.
입력
입력은 최대 50개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
첫째 줄에는 학생 수 N, 친구 관계의 개수 M, 시행 횟수 K가 주어진다. (2 ≤ N ≤ 10, 1 ≤ M ≤ N(N-1)/2, 1 ≤ K ≤ 50)
둘째 줄부터 M줄에 걸쳐 친구 관계가 주어진다. 이 중 i번째 줄에는 ai와 bi가 주어진다. (1 ≤ ai, bi ≤ N) 자기 자신과 친구인 경우는 없다. 즉, 모든 1 ≤ i ≤ M에 대해 ai ≠ bi이다. 또한, 같은 친구 관계가 여러 번 주어지지 않는다. 즉, 모든 1 ≤ i, j ≤ M에 대해 i ≠ j이면 {ai, bi} ≠ {aj, bj}이다.
입력의 마지막 줄에는 0이 3개 주어진다.
출력
각 테스트 케이스마다 정답을 한 줄로 출력한다.