CF1792F2 Graph Coloring (hard version)

本题的简单版和困难版唯一的区别在于 $ n $ 的限制。 给定一个有 $ n $ 个顶点的无向完全图。完全图是指任意两个顶点之间都有一条边相连。你需要将图中的每条边涂成红色或蓝色（每条边只能有一种颜色）。 对于一个顶点集合 $ S $，如果对于 $ S $ 中任意一对顶点 $ (v_1, v_2) $，存在一条仅经过 $ S $ 中顶点且只经过红色边的路径从 $ v_1 $ 到 $ v_2 $，则称 $ S $ 是红连通的。同理，如果对于 $ S $ 中任意一对顶点 $ (v_1, v_2) $，存在一条仅经过 $ S $ 中顶点且只经过蓝色边的路径从 $ v_1 $ 到 $ v_2 $，则称 $ S $ 是蓝连通的。 你需要对图进行染色，使得： - 至少有一条红色边； - 至少有一条蓝色边； - 对于每一个满足 $ |S| \ge 2 $ 的顶点集合 $ S $，$ S $ 要么是红连通的，要么是蓝连通的，但不能同时两者都是。 请计算有多少种不同的染色方案，并将结果对 $ 998244353 $ 取模后输出。

第一行包含一个整数 $ n $（$ 3 \le n \le 5 \cdot 10^4 $）。

输出一个整数，表示不同的染色方案数，对 $ 998244353 $ 取模。

由 ChatGPT 4.1 翻译