题目分析

本题要求我们找出 $n$ 个节点的无向图中，最多可能有多少个极大团，并对 $998244353$ 取模输出。这里的“最大团”根据图论标准术语应理解为极大团（maximal clique），即不是任何其他团的真子集的团。

我们需要的是这个数量的最大值，而不是某个特定图的具体团数。

---

核心理论：Moon–Moser 定理

1. 定理表述

1965年，Moon和Moser证明了以下重要结论：

对于 $n \ge 2$ 个顶点的无向图，极大团数量的最大值为： $ f(n) = \begin{cases} 3^{n/3} & \text{if } n \bmod 3 = 0 \\ 4 \cdot 3^{(n-4)/3} & \text{if } n \bmod 3 = 1 \\ 2 \cdot 3^{(n-2)/3} & \text{if } n \bmod 3 = 2 \end{cases} $

这个上界是紧的，即存在图达到这个数量。

2. 构造达到上界的图

达到该上界的图称为Moon–Moser图，构造方法如下：

• 当 $n \bmod 3 = 0$ 时：将顶点分成 $n/3$ 个三角形（3个顶点的完全图 $K_3$）。每个三角形内部两两相连，不同三角形之间的所有顶点也两两相连。这样每个极大团由每个三角形中选0、1、2或3个点组成？不对，实际上这种构造是：每个三角形是一个 $K_3$，三角形之间完全连接。那么一个极大团必须从每个三角形中至少选一个点吗？不是这样。

  实际上，正确构造是：将顶点分成 $n/3$ 组，每组3个点，组内无边（形成独立集），组之间全连接。这样每个极大团包含每个组中恰好一个点，所以有 $3^{n/3}$ 个极大团。

• 当 $n \bmod 3 = 1$ 时：分成 $(n-4)/3$ 个3点组和1个4点组。4点组内无边，3点组内无边，所有不同组的点之间全连边。这样，4点组中选2个点（共有6种方式），每个3点组选1个点，总数为 $4 \choose 2$ $=6$ 乘以 $3^{(n-4)/3}$？不对，Moon–Moser 构造给出的是 $4 \cdot 3^{(n-4)/3}$。

  仔细分析：4点组内无边，所以极大团不能包含4点组中超过2个点（否则它们无边）。实际上，4点组的每个点都可以与组外所有点相连，所以极大团可以包含4点组中的1个或2个点。但为了最大化数量，构造选择让每个极大团在4点组中选2个点（$C(4,2)=6$？）。但公式是4倍，不是6倍，所以可能是：4点组拆成两个2点组？不对。

  实际上，标准构造是：一个 $K_4$ 的补图（即4个点两两不相连）加上 $(n-4)/3$ 个三角形组（每组3点独立），所有不同组之间全连边。那么每个极大团在 $K_4$ 补图中选一个点（4种选择），在每个3点组中选一个点（3种），总数为 $4 \cdot 3^{(n-4)/3}$。这样更合理。

• 当 $n \bmod 3 = 2$ 时：分成 $(n-2)/3$ 个3点组和1个2点组。2点组内无边，3点组内无边，所有不同组的点之间全连边。每个极大团在2点组中选一个点（2种选择），在每个3点组中选一个点（3种），总数为 $2 \cdot 3^{(n-2)/3}$。

3. 验证样例

$n=8$ 时，$8 \bmod 3 = 2$，所以 $f(8) = 2 \cdot 3^{(8-2)/3} = 2 \cdot 3^2 = 18$，与样例输出一致。

---

定理证明思路（简化版）

Moon–Moser 的原始证明使用了归纳法。这里简述其关键思想：

归纳基础

小 $n$ 时可直接验证。

归纳步骤

设 $G$ 是有 $n$ 个顶点的图，$v$ 是 $G$ 中度数最小的顶点。令 $d = \deg(v)$，$N(v)$ 是 $v$ 的邻居集合，$G' = G \setminus (\{v\} \cup N(v))$。

关键观察：

1. 每个极大团要么包含 $v$，要么不包含 $v$。
2. 包含 $v$ 的极大团，去掉 $v$ 后是 $G[N(v)]$ 的极大团。
3. 不包含 $v$ 的极大团，是 $G \setminus \{v\}$ 的极大团。

设 $m_k(n)$ 表示 $n$ 个顶点且最小度至少为 $k$ 的图的极大团数最大值。 通过分析 $d$ 的大小情况，可以证明递推关系，最终得出上述闭式解。

---

特殊情况和边界

• $n=0$：没有顶点，按定义有 $1$ 个团（空集），但空集是不是极大团？通常空集不是团（因团要求顶点集合非空？定义中没说非空，但一般图论中团是非空顶点集）。但 $n=0$ 时极大团数量为 $0$。从公式看：$0 \bmod 3 = 0$，$3^{0/3}=1$，与 $0$ 冲突。所以要特殊处理 $n=0$ 输出 $0$（或根据题意 $n=0$ 时没有团，输出 $0$）。

• $n=1$：$1 \bmod 3 = 1$，$4 \cdot 3^{(1-4)/3}$ 指数为负，无意义。所以要单独处理小 $n$。

  实际上 $n=1$ 时，只有一个顶点，只有一个团 $\{v_1\}$，也是极大团，所以 $f(1)=1$。

• $n=2$：$2 \bmod 3 = 2$，$2 \cdot 3^{(2-2)/3} = 2 \cdot 3^0 = 2$，正确：两个点无边时有两个单点极大团；有边时只有一个2点极大团，最大是2。

• $n=3$：$3 \bmod 3 = 0$，$3^{1}=3$，正确：三角形有1个极大团（整个图），但3点独立集有3个单点极大团，所以最大是3。

由此可知公式对 $n \ge 2$ 有效，$n=0,1$ 单独处理。

---

算法实现要点

给定 $n$ 最大 $10^{18}$，直接计算 $3^{\lfloor n/3 \rfloor}$ 等需要快速幂取模。

1. 计算步骤

1. 读入 $n$。
2. 如果 $n=0$，输出 $0$。
3. 如果 $n=1$，输出 $1$。
4. 否则计算 $r = n \bmod 3$：
   • 若 $r=0$：$ans = 3^{n/3} \bmod M$
   • 若 $r=1$：$ans = 4 \cdot 3^{(n-4)/3} \bmod M$
   • 若 $r=2$：$ans = 2 \cdot 3^{(n-2)/3} \bmod M$
5. 输出 $ans$。

2. 模运算细节

$M = 998244353$ 是质数，可以用快速幂 $O(\log n)$ 时间计算 $3^k \bmod M$。

注意 $(n-4)/3$ 和 $(n-2)/3$ 在整数除法下是整除，因为 $n \bmod 3=1$ 时 $n-4$ 能被3整除，$n \bmod 3=2$ 时 $n-2$ 能被3整除。

---

数学推导：为什么是3的幂？

直观理解：为了最大化极大团数量，我们希望图的结构尽可能“对称”，使得每个顶点在尽可能多的极大团中出现。通过将顶点分组，组内无边（保证组内点不能同时出现在一个团中），组间全连边（保证不同组的点可以任意组合），这样每个极大团从每组中选至多一个点（实际上恰好一个点，因为如果一组中不选点，那么可以从该组加一个点仍然形成团，矛盾，所以必须每组选一个点）。

因此，极大团的数量等于每组选择的方案数乘积。为了最大化乘积，在总和固定时，根据均值不等式，各组的方案数应尽量接近。方案数就是组的大小（因为组内点互相无边，所以只能选一个点）。

设组大小为 $x_1, x_2, \dots, x_k$，$\sum x_i = n$，极大团数 = $\prod x_i$。在 $x_i \ge 1$ 整数约束下，最大乘积在 $x_i$ 尽可能为 $3$ 时取得（因为 $3$ 比 $2$ 和 $4$ 在乘积上更优：$3 \times 3 > 2 \times 2 \times 2$，$4 < 3 \times 1$ 但这里不允许 $1$？）。
严格推导：比较 $a \ge 4$ 时，拆成 $2$ 和 $a-2$：$2(a-2) \ge a$ 当 $a \ge 4$ 时成立，所以大于 $3$ 的组不如拆成 $2$ 和 $a-2$。而 $2 \times 2 \times 2 = 8 < 3 \times 3 = 9$，所以 $3$ 是最优的组大小。

因此最优分组是尽量多 $3$，余数 $1$ 时把一个 $3$ 拆成 $2+2$（乘积 $3^{k-1} \times 4$），余数 $2$ 时加一个 $2$（乘积 $3^k \times 2$）。这就是 Moon–Moser 公式的组合解释。

---

总结

本题是一个直接应用 Moon–Moser 定理的题目，难点在于：

1. 知道该定理的存在（属于图论极值问题的经典结论）。
2. 正确处理 $n=0,1$ 的边界情况。
3. 对极大的 $n$ 进行快速幂取模计算。

通过这题，我们学习了：

• 无向图极大团数量的上界定理。
• 如何构造达到上界的图。
• 组合极值中“分组乘积最大化”的典型方法。

最终算法时间复杂度 $O(\log n)$，空间 $O(1)$，可以轻松处理 $n \le 10^{18}$ 的情况。