CF1989E Distance to Different 题解

题意回顾

给定整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$，$2 \le k \le \min(n, 10)$）。构造一个长度为 $n$ 的数组 $a$，其中每个元素 $a_i \in [1, k]$，且 $1 \sim k$ 每个整数至少出现一次。

由 $a$ 生成数组 $b$：$b_i = \min\limits_{j \in [1,n],\, a_j \neq a_i} |i - j|$，即 $b_i$ 是到最近的 与 $a_i$ 不同的元素 的距离。

求在所有满足条件的 $a$ 中，不同的 $b$ 数组有多少个，答案对 $998244353$ 取模。

---

核心观察：$b$ 数组的结构

设 $a$ 中颜色变化的边界位置集合为 $S = \{ i \mid a_i \neq a_{i+1} \}$。对于一段连续相同颜色的区间 $[L, R]$，有：

• 若 $i$ 是边界（$L$ 或 $R$），且另一侧存在不同颜色，则 $b_i = 1$；
• 若 $i$ 在区间内部，则 $b_i = \min(i - L + 1,\, R - i + 1)$。

因此 $b$ 数组完全由 每个颜色段的长度 和 边界的位置 决定。具体来说：

• 相邻两段之间必然有 $b_{L-1}=b_R=1$（若边界不在数组首尾）。
• 在段内部，$b$ 值从边界向中间每次 $+1$，形成“山峰”形状。
• 不可能出现两个相邻的 $1$（否则中间那段长度为 $0$，不合法）。唯一的例外是数组末尾位置 $n$：如果最后一段长度恰好为 $1$，则 $b_{n-1}=1$ 且 $b_n=1$，这是允许的。

综上，一个合法的 $b$ 数组等价于选择一组“$1$ 的位置”（标记颜色变化），满足：

1. 任意两个 $1$ 之间至少间隔一个位置（除非在末尾可以连续）；
2. $1$ 的个数决定了段数，段数必须 $\ge k$（因为要使用至少 $k$ 种颜色，且相邻段颜色不同）。

给定 $1$ 的位置后，$b$ 数组的其他位置被唯一确定：两个 $1$ 之间的区间填成递增再递减的“山峰”。

因此问题转化为：统计选择 $1$ 的位置的方案数，满足段数 $\ge k$，且相邻段颜色不同的染色方案数。由于 $k \le 10$，我们可以用 DP 同时处理段的划分和颜色分配。

---

DP 状态设计

设 $f[i][j]$ 表示：考虑前 $i$ 个位置，恰好形成了 $j$ 个颜色段，且第 $i$ 个位置恰好是一个段的末尾（即 $b_i = 1$ 或 $i=n$ 时允许末尾不是 $1$）的方案数。

为了正确转移，我们维护前缀和 $sum[i][j] = \sum_{t=0}^{i} f[t][j]$，含义是“前 $i$ 个位置中，最后一个段结束位置 $\le i$ 且段数为 $j$ 的方案数”。

初始状态：$f[0][0] = sum[0][0] = 1$，表示空序列有 $0$ 段。

转移：

当我们考虑第 $i$ 个位置作为当前段的末尾时，设其前一个段结束于位置 $p$（$p < i$，且当 $i<n$ 时不能有 $p = i-1$，否则出现相邻的 $1$），那么段数增加 $1$，并且我们需要为新段分配一种颜色（不同于前一段的颜色）。由于颜色分配与 $b$ 的形状无关，并且我们只关心最终使用了多少种不同颜色，因此 $j$ 直接表示段数即可（段数 $\ge$ 使用颜色数，最后再乘组合数？这里实际上在 DP 内部已经隐含了颜色分配的因子，具体看下文）。

核心转移式（$1 \le j \le k$）：

$$f[i][j] = sum[i-1][j-1] \quad-\quad [i>2 \land i \neq n] \cdot f[i-2][j-1] $$

其中 $- f[i-2][j-1]$ 是减去 $p = i-1$ 的情况（相邻的 $1$，非法），但当 $i=n$ 时允许相邻（最后一段长 $1$），因此不做减法。当 $i \le 2$ 时也不可能出现合法的相邻 $1$，故也不减。

对于 $j = k+1$ 的情况（段数超过 $k$ 也是允许的，只要颜色数达到 $k$），转移中需要合并全部段数 $\ge k$ 的状态：

$$f[i][k+1] = sum[i-1][k] + sum[i-1][k+1] \quad-\quad [i>2 \land i \neq n] \cdot \bigl(f[i-2][k] + f[i-2][k+1]\bigr) $$

这代表“前 $i-1$ 个位置已经有了 $k$ 段或 $k+1$ 段，现在新开一段（或末尾闭合）”的总和，同样减去非法相邻情况。

前缀和维护：

$$sum[i][j] = \bigl(sum[i-1][j] + f[i][j]\bigr) \bmod p $$

其中 $sum[i][0] = 1$ 恒成立。

---

答案计算

DP 结束后，要求段数 $\ge k$ 且每种颜色至少出现一次。对于恰好 $k$ 段的情况，段数等于颜色数，染色方案唯一（相邻段颜色不同，且 $k$ 种颜色全用，必须是排列 $k$ 种颜色的某种交替模式）。对于 $>k$ 段的情况，我们需要保证 $k$ 种颜色都出现，这等价于段数 $\ge k$ 的合法 $b$ 序列都对应了有效的颜色分配（因为总可以给多余的段重复某些颜色）。实际上，通过组合推导可以得到：最终合法的 $b$ 数组数量恰好等于

$$f[n][k] + f[n][k+1]$$

其中 $f[n][k]$ 对应恰好 $k$ 段（颜色全用），$f[n][k+1]$ 对应段数 $>k$ 的所有情况（被 $k+1$ 状态吸收）。这是因为 DP 中的 $j$ 直接对应段数，而颜色分配方案已隐含在转移中（相邻段必须不同颜色，保证了至少需要 $k$ 种颜色；段数 $\ge k$ 必然可以分配满 $k$ 种颜色）。

---

复杂度

• 状态数 $O(nk)$，其中 $k \le 10$，$n \le 2\cdot 10^5$。
• 转移 $O(1)$，总复杂度 $O(nk)$，非常轻松。

---

参考代码

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 200010;
const long long p = 998244353;

int n, k;
long long f[N][12], sum[N][12];

int main() {
    cin >> n >> k;
    f[0][0] = sum[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        sum[i][0] = 1;                     // 0 段只有空集
        for (int j = 1; j <= k; j++) {
            // 新开一段，从前 i-1 个位置中段数为 j-1 的状态转移
            f[i][j] = sum[i-1][j-1];
            if (i > 2 && i != n)
                f[i][j] = (f[i][j] - f[i-2][j-1] + p) % p; // 减去相邻 1 的非法情况
            else
                f[i][j] = (f[i][j] + p) % p;
            sum[i][j] = (sum[i-1][j] + f[i][j]) % p;
        }

        // 处理段数 >= k 的情况 (k+1 状态)
        f[i][k+1] = (sum[i-1][k] + sum[i-1][k+1]) % p;
        if (i > 2 && i != n)
            f[i][k+1] = (f[i][k+1] - (f[i-2][k] + f[i-2][k+1]) % p + p) % p;
        sum[i][k+1] = (sum[i-1][k+1] + f[i][k+1]) % p;
    }

    long long ans = (f[n][k] + f[n][k+1]) % p;
    cout << ans << endl;
    return 0;
}

注意：模数 $998244353$ 是质数，代码中的减法均加上 $p$ 保证非负。