专栏文章

题解：CF1158F Density of subarrays

PPengzt
CF1158F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqjfazm
此快照首次捕获于
2025/12/04 05:47
3 个月前
此快照最后确认于
2025/12/04 05:47
3 个月前
查看原文

Density of subarrays

题目链接。cnblogs。

Problem

我们定义一个“cc 序列”为序列里的数都是 [1,c][1, c] 的序列。定义一个 cc 序列的“密度”为最大的 pp，使得任意长度为 pp 的序列（总共 cpc^p 个）都是它的子序列。
给定一个长度为 nn 的“cc 序列”，对 p∈[0,n]p \in [0, n]，求该序列有多少个子序列的密度为 pp，答案对 998244353998244353 取模。
数据范围：n,m≤3000n, m \le 3000。

Sol

感觉这道题难点在于知道复杂度！如果这个题被扔到 OI 里，给两个部分分是不是就完全没难度了。
先考虑一下如何判定一个序列的密度。这是一个很简单的贪心。假如之前已经匹配到 ii，由于是任意长度为 pp 的序列，所以肯定是尽量往后找。即找到第一个使得 [i,j][i, j] 中出现 1∼c1 \sim c 所有数的位置 jj，然后让答案增加一，继续进行刚才的操作，无法再找到下一个 jj 时结束。于是就有一个很简单的 DP：定义 fi,jf_{i, j} 表示填了 ii 个数，密度为 jj 的方案数。则有转移 fi,j=∑k<ifk,j−1⋅w(k+1,i)f_{i, j} = \sum\limits_{k < i}f_{k, j - 1} \cdot w(k + 1, i)，其中 w(l,r)w(l, r) 表示 al,al+1,…,ara_l, a_{l + 1}, \dots, a_r 中有多少个子序列满足 1∼n1 \sim n 中的数都出现了至少一次。w(i,j)w(i, j) 是好算的，可以 O(n2)\mathcal{O}(n^2) 预处理出。然后这就得到了一个很简单的 O(n3)\mathcal{O}(n^3) 的做法。然后发现这道题 n≤3000n \le 3000 还开了六秒，肯定就不是 O(n2)\mathcal{O}(n^2) 的。仔细分析一下刚才做法的复杂度。不难发现，当 p>ncp > \frac nc 时，答案一定为 00，所以刚才 DP 的第二维是 O(nc)\mathcal{O}(\frac nc) 的，于是这个 DP 就变成了 O(n3c)\mathcal{O}(\frac{n^3}{c}) 了。于是发现只有这个 cc 比较小的时候才会跑的比较慢，想一下 cc 比较小咋做。
不难得出一个暴力 DP：gi,j,Sg_{i, j, S} 表示填了 ii 个数，当前密度为 pp，1∼c1 \sim c 中的数填过的集合为 SS 的方案数。转移是很简单的，枚举 aia_i 选不选就行了。然后这个东西的时间复杂度是 O(n⋅nc⋅2c)\mathcal{O}(n\cdot \frac nc \cdot 2^c) 的。当 n22cc=n3c\frac{n^22^c}{c} = \frac{n^3}{c} 时，c=log⁡2nc = \log_2 n。所以 cc 取 1010 左右比较好。最后的时间复杂度变为 O(n3log⁡n)\mathcal{O}(\frac{n^3}{\log n})。

Code

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template<typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
const int P = 998244353;
ll QPow(ll a, ll b) {
	ll res = 1;
	for (; b; a = a * a % P, b >>= 1)
		if (b & 1)
			res = res * a % P;
	return res;
}
int n, c;
int a[3005];
namespace SolveB {
int cnt, buc[3005];
ll g[3005][3005], h[3005], pw2[3005], ipw1[3005], ipw2[3005];
unsigned long long f[3005][3005];
void Work() {
	pw2[0] = 1;
	for (int i = 1; i <= n; i++)
		pw2[i] = pw2[i - 1] * 2 % P;
	for (int i = 0; i <= n; i++)
		ipw1[i] = QPow((pw2[i] + P - 1) % P, P - 2),
		ipw2[i] = QPow(pw2[i], P - 2);
	for (int l = 1; l <= n; l++) {
		memset(buc, 0, sizeof (buc));
		ll res = 1;
		for (int r = l; r <= n; r++) {
			if (buc[a[r]])
				res = res * ipw1[buc[a[r]]] % P;
			else
				cnt++;
			buc[a[r]]++;
			res = res * (pw2[buc[a[r]]] + P - 1) % P;
			if (cnt == c)
				g[l][r] = res * ipw1[buc[a[r]]] % P;
		}
		cnt = 0;
	}
	memset(buc, 0, sizeof (buc));
	cnt = 0;
	ll all = 1, res = 1;
	h[n + 1] = 1;
	for (int i = n; i; i--) {
		all = all * ipw2[buc[a[i]]] % P;
		if (buc[a[i]])
			res = res * ipw1[buc[a[i]]] % P;
		else
			cnt++;
		buc[a[i]]++;
		all = all * pw2[buc[a[i]]] % P;
		res = res * (pw2[buc[a[i]]] + P - 1) % P;
		h[i] = (all + P - (cnt == c ? res : 0)) % P;
	}
	f[0][0] = 1;
	for (int i = 1; i * c <= n; i++)
		for (int j = c * i; j <= n; j++) {
			for (int k = (i - 1) * c; k <= n && g[k + 1][j]; k++) {
				f[i][j] += f[i - 1][k] * g[k + 1][j];
				if (!(k & 15))
					f[i][j] %= P;
			}
			f[i][j] %= P;
		}
	for (int i = 0; i <= n; i++) {
		ll ans = 0;
		for (int j = c * i; j <= n; j++)
			(ans += f[i][j] * h[j + 1]) %= P;
		if (i * c > n)
			ans = i == 0;
		printf("%lld%c", ans - (i == 0), " \n"[i == n]);
	}
}
}
namespace SolveS {
int f[2][3005][1 << 10];
void Work() {
	for (int i = 1; i <= n; i++)
		a[i]--;
	f[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		int o = i & 1;
		for (int j = 0; j * c <= i; j++)
			for (int S = 0; S < (1 << c); S++) {
				(f[o ^ 1][j][S] += f[o][j][S]) %= P;
				if ((S | (1 << a[i + 1])) == (1 << c) - 1)
					(f[o ^ 1][j + 1][0] += f[o][j][S]) %= P;
				else
					(f[o ^ 1][j][S | (1 << a[i + 1])] += f[o][j][S]) %= P;
			}
		for (int j = 0; j * c <= i; j++)
			for (int S = 0; S < (1 << c); S++)
				f[o][j][S] = 0;
	}
	for (int i = 0; i <= n; i++) {
		int ans = 0;
		for (int S = 0; S < (1 << c); S++)
			(ans += f[n & 1][i][S]) %= P;
		printf("%d%c", (ans + P - (i == 0)) % P, " \n"[i == n]);
	}
}
}
int main() {
	scanf("%d%d", &n, &c);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	if (c > 10)
		return SolveB::Work(), 0;
	SolveS::Work();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...