ARC100F Colorful Sequences 题解

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;
}