计数 123：题解

思路

数列中唯一不允许的相邻对是 $(1,3)$ 和 $(3,1)$。先删去所有的 $2$，得到一个只含 $1,3$ 的序列 $B$。设 $B$ 中相邻元素不同的位置有 $r$ 个。

把 $X_2$ 个 $2$ 放回 $B$ 的 $X_1+X_3+1$ 个空隙。上述 $r$ 个发生颜色切换的内部空隙必须至少放一个 $2$，其余空隙可以为空。先给这 $r$ 个空隙各放一个 $2$，再用隔板法分配剩余的 $X_2-r$ 个 $2$，方案数为

$$\binom{X_1+X_2+X_3-r}{X_1+X_3}.$$

因此只需计算：固定 $X_1$ 个 $1$ 和 $X_3$ 个 $3$ 时，恰有 $r$ 次颜色切换的二元序列有多少个。

做法

若 $r=2k-1$，首尾颜色不同，两种颜色都恰有 $k$ 段。把 $X_1$ 个 $1$ 和 $X_3$ 个 $3$ 分别拆成 $k$ 个非空段，且可以选择以哪种颜色开头，方案数为

$$2\binom{X_1-1}{k-1}\binom{X_3-1}{k-1}.$$

若 $r=2k$，首尾颜色相同。以 $1$ 开头并结尾时，$1$ 有 $k+1$ 段、$3$ 有 $k$ 段；交换两种颜色得到另一种情况。方案数为

$$\binom{X_1-1}{k}\binom{X_3-1}{k-1} +\binom{X_1-1}{k-1}\binom{X_3-1}{k}.$$

枚举 $1\le r\le \min(X_2,X_1+X_3-1)$，将二元序列数乘上放回 $2$ 的方案数并求和即可。

组合数中的最大上标不超过 $X_1+X_2+X_3\le 3\times10^6<998244353$，预处理阶乘与逆阶乘后，每项可以 $O(1)$ 求出。

正确性证明

删除所有 $2$ 后，原序列唯一对应于一个二元序列 $B$，以及每个空隙中被删除的 $2$ 的个数。若 $B$ 的一个相邻位置由 $1$ 切换为 $3$ 或由 $3$ 切换为 $1$，该空隙必须非空；否则原序列会出现禁止的相邻对。反之，只要所有切换空隙非空，原序列中所有相邻元素之差都不超过 $1$。所以固定 $B$ 后，隔板法给出的数量既无遗漏也无重复。

一个恰有 $r$ 次切换的二元序列恰有 $r+1$ 个非空同色段。奇偶两种公式分别枚举首尾异色与首尾同色的全部可能，并用正整数拆分组合数确定各段长度，因此也无遗漏、无重复。对所有可行的 $r$ 求和即得到全部合法序列数。

复杂度

预处理阶乘为 $O(X_1+X_2+X_3)$，枚举切换次数为 $O(\min(X_2,X_1+X_3))$，空间复杂度为 $O(X_1+X_2+X_3)$。