연결된 라벨 그래프의 셈
다이아몬드 I의견: 0
정점에 \(1\) 부터 \(n\) 까지 서로 다른 번호가 붙어 있는, 단순하고 무향인 라벨 그래프를 생각하자. 정점이 \(n\) 개일 때 가능한 모든 라벨 그래프의 수는 \(2^{\binom{n}{2}}\) 이다(각 정점 쌍마다 간선의 유무를 자유롭게 정한다).
이 중에서 연결되어 있는 그래프, 즉 임의의 두 정점 사이에 경로가 존재하는 그래프의 수를 \(f(n)\) 이라 하자.
정수 \(N\) 이 주어지면, \(f(1), f(2), \dots, f(N)\) 을 모두 \(998244353\) 으로 나눈 나머지로 차례대로 구하여라.
\(1 \le N \le 100{,}000\)
첫 줄에 정수 \(N\) 이 주어진다.
\(N\) 개의 줄에 걸쳐 \(f(1), f(2), \dots, f(N)\) 을 한 줄에 하나씩, \(998244353\) 으로 나눈 나머지로 출력한다.
4
1
1
4
38\(f(1)=1\) (정점 하나). \(f(2)=1\) (유일한 간선이 있어야 연결). \(f(3)=4\) (전체 \(2^3=8\) 중 연결된 것 4가지). \(f(4)=38\).
1
1정점이 하나뿐이면 그 자체로 연결이며 그래프는 하나, \(f(1)=1\).
riseoj 작성
출처 Original
평가 및 의견
연결된 라벨 그래프의 셈
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
연결된 라벨 그래프의 셈