그래프 세기
시간 제한5초메모리 제한512 MB
정점 2n개를 가진 무향 그래프 중 완전 매칭이 없지만 어떤 없는 변을 하나 추가하면 완전 매칭이 생기는 그래프의 동형류 개수를 998244353으로 나눈 나머지로 구한다.
문제
루프와 중복 간선이 없는 2n개의 정점 위의 무방향 그래프를 생각하자. 그래프 G가 good하다는 것은 G에 완전 매칭이 없지만, G에 속하지 않는 임의의 간선을 G에 추가하면 그 결과 그래프에 완전 매칭이 생기는 것을 말한다.
2n개의 정점 위의 서로 다른 good 그래프의 개수를 998 244 353으로 나눈 나머지를 구하라.
두 그래프가 다르다는 것은 서로 동형이 아니라는 뜻이다. 즉, 정점의 이름을 바꾸는 것으로 한 그래프를 다른 그래프로 만들 수 없다.
입력
첫째 줄에 정수 n이 주어진다. (1 ≤ n ≤ 500 000) 2n은 그래프의 정점 수이다.
출력
2n개의 정점 위의 서로 다른 good 그래프의 개수를 998 244 353으로 나눈 나머지를 한 줄에 출력한다.
힌트
2n = 4인 경우의 그래프:
