[Easy-Medium] CF1989E Distance to Different

简要题意

对于一个长度为 $n$ 的序列 $a$，定义 $a$ 的生成序列 $b$ 为一个长度为 $n$ 的序列，且满足：

$$b_i = \min_{j\in[1,n], a_i\neq a_j} |i-j|$$

我们称一个序列是好的，当且仅当值域恰好为 $[1,k]$。你需要求所有长度为 $n$ 的好的序列的生成序列数量。相同的序列仅计算一次。

$2\leq n\leq 2\times 10^5,2\leq k\leq\min(n,10)$。

思路

先来考虑长度为 $n$ 的序列的生成序列数量，由于 $b_i$ 的意义其实是 $a_i$ 到最近的与 $a_i$ 不同的 $a_j$ 的距离，所以对于一个长度为 $L$ 的颜色段，$b_i$ 应当形如 $1,\cdots,\lfloor\frac{L}{2}\rfloor,\lceil\frac{L}{2}\rceil,\cdots,1$。特别地，若颜色段位于开头或结尾，则为 $L,L-1,\cdots,1$ 以及 $1,2,\cdots,L$。这启示我们将 $b$ 划分为若干段，则每一段对应 $a$ 的颜色段，且 $b$ 中该段的填数只和 $L$ 和是否位于开头结尾有关。

dp，设 $F(i)$ 表示长度为 $i$ 的序列的生成序列数量，不难有转移：

$$F(i)=\sum_{k=0}^{i-1} F(k)$$

这样会算重，原因是对于不为首尾的长度为 $2$ 的段，则形如 $1,1$，和两个长度为 $1$ 的段一致，所以需要排除这种情况：

$$F(i)=\sum_{k=0}^{i-1}[i=1\lor i=n\lor k-i\neq 2] F(k)$$

用前缀和优化转移，时间复杂度 $O(n)$。

然后考虑值域的限制，只需要将序列分成至少 $k$ 段即可，只需要在 $F$ 的基础上加一维表示划分的段数即可。

时间复杂度 $O(n^2)$，考虑优化，改为用全集减去分成少于 $k$ 段的方案即可做到 $O(nk)$。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 2e5 + 5;
int n, k, dp[N], f[N][15], g[N][15], sumt[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    dp[0] = sumt[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = sumt[i - 1];
        if(i >= 2 && i != 2 && i != n) dp[i] = Sub(dp[i], dp[i - 2]);
        sumt[i] = Add(sumt[i - 1], dp[i]);
    }
    f[0][0] = g[0][0] = 1;
    for(int i=1;i<=n;i++){
        g[i][0] = g[i - 1][0];
        for(int j=1;j<=min(k-1,i);j++){
            f[i][j] = g[i - 1][j - 1];
            if(i >= 2 && i != 2 && i != n) f[i][j] = Sub(f[i][j], f[i - 2][j - 1]);
            g[i][j] = Add(g[i - 1][j], f[i][j]);
        }
    }
    int ans = 0;
    for(int i=1;i<k;i++) ans = Add(ans, f[n][i]);
    cout << Sub(dp[n], ans) << '\n';
    return 0;
}

// Written by xiezheyuan