ARC100F Colorful Sequences 题解

作者: xht37 分类: 题解 发布时间: 2020-04-26 17:23

点击数:117

ARC100F Colorful Sequences

题意

  • 给定 $n,k$ 和序列 $a_{1\dots m}$。
  • 定义存在「长度为 $k$ 的连续子序列是一个连续段」的序列为 colorful 序列。
  • 求所有长度为 $n$ 值域 $[1,k]$ 的 colorful 序列的所有连续子序列中有多少个恰好是 $a_{1 \dots m}$。
  • $n \le 2.5 \times 10^4$,$k \le 400$,答案对 $10^9+7$ 取模。

题解

答案等于所有序列的答案减去不 colorful 序列的答案。

前者答案为 $k^{n-m}(n-m+1)$,考虑如何计算后者,即计算不 colorful 序列中 $a_{1\dots m}$ 的个数。

先考虑一个这样一个问题:计算不 colorful 序列的个数。

考虑 DP,设 $f_{i,j}$ 表示考虑前 $i$ 个数,当前极长的没有重复数的后缀长度为 $j$ 的方案数。

初始状态为 $f_{0,0} = 1$,目标答案为 $\sum_{j=0}^{k-1} f_{n,j}$,转移如下:
$$
f_{i,j} \leftarrow f_{i-1,j^\prime} \cdot\begin{cases}0 & j^\prime + 1 < j \\k – j^\prime & j^\prime + 1 = j \\1 & j^\prime + 1 > j\end{cases}
$$
复杂度 $\mathcal O(nk^2)$,前缀和优化一下为 $\mathcal O(nk)$。

接下来考虑原问题:计算不 colorful 序列中 $a_{1\dots m}$ 的个数。

考虑三种情况:

  1. $a_{1\dots m}$ 本身就是 colorful 序列,答案显然为 $0$。
  2. 否则,若 $a_{1\dots m}$ 中的数互不相同,但由于 $m<k$ 所以不是 colorful 序列。
    考虑计算不 colorful 序列中「长度为 $m$ 的其中的数互不相同的连续子序列」个数,然后除以 $k^{\underline{m}}$ 就是答案。
    计算方法就是上面的 DP,另外定义一个 $g_{i,j}$ 表示 $f_{i,j}$ 中 $a_{1\dots m}$ 的个数,当 $j \ge m$ 时让 $g_{i,j}$ 加上 $f_{i,j}$,然后一起转移即可。
  3. 否则,意味着 $a_{1 \dots m}$ 中有相同的数且不是 colorful 序列。
    先求出极长的没有重复数的前后缀长度,设为 $l,r$。
    同样采用上面的 DP,只是将初值改成 $f_{0,l} = 1$,同理设 $g_{0,r} = 1$。
    枚举 $a_{1\dots m}$ 的开头位置 $i$,则方案数为 $\left(\sum_{j=0}^{k-1} f_{i-1,j}\right)\left(\sum_{j=0}^{k-1} g_{n-(i-1)-m,j}\right)$。

总时间复杂度 $\mathcal O(nk)$。

代码

const int N = 2.5e4 + 7, K = 407;
int n, k, m, a[N], l, r;
bool v[K];
modint f[N][K], g[N][K], ans;

inline void clear() {
    for (int i = 1; i <= k; i++) v[i] = 0;
}

inline bool pd(int l, int r) {
    clear();
    for (int i = l; i <= r; i++)
        if (v[a[i]]) return 0;
        else v[a[i]] = 1;
    return 1;
}

inline bool colorful() {
    for (int l = 1, r = k; r <= m; l++, r++)
        if (pd(l, r)) return 1;
    return 0;
}

inline void DP(modint f[N][K]) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < k; j++)
            f[i][j] = (f[i-1][j-1] - f[i-1][j]) * (k - j + 1) + f[i-1][j];
        for (int j = k - 1; ~j; j--) f[i][j] += f[i][j+1];
    }
}

int main() {
    rd(n, k, m), rda(a, m);
    if (colorful()) return print(((modint)k ^ (n - m)) * (n - m + 1)), 0;
    clear();
    for (int i = 1; i <= m; i++)
        if (v[a[i]]) break;
        else v[a[i]] = 1, ++l;
    clear();
    for (int i = m; i; i--)
        if (v[a[i]]) break;
        else v[a[i]] = 1, ++r;
    if (l == m) {
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < k; j++)
                f[i][j] = (f[i-1][j-1] - f[i-1][j]) * (k - j + 1) + f[i-1][j],
                g[i][j] = (g[i-1][j-1] - g[i-1][j]) * (k - j + 1) + g[i-1][j] + (j >= m) * f[i][j];
            for (int j = k - 1; ~j; j--)
                f[i][j] += f[i][j+1], g[i][j] += g[i][j+1];
        }
        ans = g[n][0];
        for (int i = k; i > k - m; i--) ans /= i;
    } else {
        for (int i = 0; i <= l; i++) f[0][i] = 1;
        for (int i = 0; i <= r; i++) g[0][i] = 1;
        DP(f), DP(g);
        for (int i = 1, j = m; j <= n; i++, j++)
            ans += f[i-1][0] * g[n-j][0];
    }
    print((((modint)k ^ (n - m)) * (n - m + 1)) - ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注