题解与来源题共享。已有题解默认通过；新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域：system

• 0

  CYS LV 10 MOD @ 2026-10-4 16:35:12

  1. 前置思考

  题目要求我们在恰好 $k$ 次操作后，得到尽可能多的、长度完全相同的胡萝卜。 假设我们最终希望得到的大量相同胡萝卜的长度为 $v$。

  每次操作，我们可以选择一个集合，并指定一个 $x$。如果胡萝卜长度 $L > x$，它就会被切成 $x$ 和 $L-x$。 因为我们可以选择任意集合的胡萝卜同时操作，这意味着在 $1$ 次操作中，我们可以把选中的每一段都切成两半。 这就像细胞分裂一样：

  • $1$ 次操作后，$1$ 根胡萝卜最多变成 $2^1 = 2$ 根。
  • $2$ 次操作后，最多变成 $2^2 = 4$ 根。
  • $k$ 次操作后，$1$ 根胡萝卜最多变成 $2^k$ 根。

  假设有一根初始长度为 $L$ 的胡萝卜，我们想用 $k$ 次操作从中提取出尽量多长度为 $v$ 的段。 最贪心、最高效的切法是二分切割

  • 第 $1$ 次操作选 $x = 2^{k-1}v$
  • 第 $2$ 次操作选 $x = 2^{k-2}v$
  • ……
  • 第 $k$ 次操作选 $x = v$

  通过这种方式，我们能在 $k$ 次操作内，把长度充分利用，并行地切出大量长度为 $v$ 的段。

  ---

  2. 单根胡萝卜的极限推导

  对于单根长度为 $L$ 的胡萝卜，目标是切出长度为 $v$ 的段。我们最多能切出多少段？ 显然，从长度上限制，最多只能切出 $j = \lfloor \frac{L}{v} \rfloor$ 段。 但由于操作次数 $k$ 的限制，我们最多只能产生 $2^k$ 个碎块。我们分三种情况讨论：

  情况 A：$L < 2^k \cdot v$ （即 $j \le 2^k - 1$）

  因为理论最多只能切出 $j$ 段，且 $j < 2^k$。我们在 $k$ 次操作内完全有能力把这 $j$ 段全部分离出来。

  • 结论： 贡献了 $\lfloor \frac{L}{v} \rfloor$ 段。

  情况 B：$L = 2^k \cdot v$

  这是一根非常完美的胡萝卜。我们按照上述的二分切割法，每次对半切，$k$ 次操作后，刚好切成 $2^k$ 个碎块，且每个碎块的长度恰好都是 $v$。没有任何浪费。

  • 结论： 贡献了 $2^k$ 段。

  情况 C：$L > 2^k \cdot v$

  此时胡萝卜非常长。我们在 $k$ 次操作后最多只能把它切成 $2^k$ 个碎块。 这 $2^k$ 个碎块的长度总和是 $L$。因为 $L > 2^k \cdot v$，根据鸽巢原理，不可能所有碎块的长度都是 $v$（否则总长只有 $2^k \cdot v$）。 也就是说，至少有 1 个碎块的长度 $> v$。因此，长度恰好为 $v$ 的碎块数量最多只能是 $2^k - 1$。 （通过贪心二分切割，我们确实可以做到留下 $1$ 块较长的废料，其余 $2^k - 1$ 块全是 $v$）。

  • 结论： 贡献了 $2^k - 1$ 段。

  ---

  3. 算法设计与优化

  理解了单根胡萝卜的贡献规则后，我们现在要对所有的胡萝卜求和。 假设当前枚举的目标长度为 $v$，操作次数为 $k$。令 limit $= 2^k - 1$。 根据上面的推导，一根长度为 $L$ 的胡萝卜的贡献如下：

  1. 如果 $\lfloor \frac{L}{v} \rfloor \le \text{limit}$：贡献为 $\lfloor \frac{L}{v} \rfloor$。
  2. 如果 $L = (\text{limit} + 1) \cdot v$：贡献为 $\text{limit} + 1$ （也就是 $2^k$）。
  3. 如果 $L > (\text{limit} + 1) \cdot v$：贡献为 $\text{limit}$ （也就是 $2^k - 1$）。

  为什么 $k$ 最大只考虑到 17？

  题目中 $m \le 2 \times 10^5$。 当 $k = 18$ 时，$2^{18} = 262144 > 200000 \ge m$。 这意味着对于 $k \ge 18$，所有的胡萝卜都属于情况 A，我们可以把所有胡萝卜都切成长度为 $1$ 的段。此时能得到的最多段数就是所有初始胡萝卜长度之和（$\sum a_i$）。 因此，对于 $k > 17$ 的询问，答案恒为 sum_a，我们只需计算 $k \in [1, 17]$。

  调和级数枚举优化

  为了快速计算，我们可以预处理：

  • cnt[x]：长度为 $x$ 的胡萝卜数量。
  • s[x]：cnt[x] 的前缀和，用于快速查询区间内的胡萝卜总数。

  对于固定的 $v$，我们枚举 $j = 1, 2, \dots, \lfloor \frac{m}{v} \rfloor$。 落在区间 $[j \cdot v, (j+1) \cdot v - 1]$ 内的所有胡萝卜，它们的 $\lfloor \frac{L}{v} \rfloor$ 都是 $j$。 我们预处理一个数组 sumj：

  • sumj[j] 表示：所有 $\lfloor \frac{L}{v} \rfloor \le j$ 的胡萝卜，如果完全按照情况 A 提取，总共能提供多少段。

  然后在计算固定的 $v$ 和 $k$ 时，我们直接根据上面的 $3$ 种情况，使用 sumj 和前缀和 s 以 $O(1)$ 的时间算出总贡献。最后所有 $v$ 取最大值即可。

  ---

  4. Std

  #include <bits/stdc++.h>
  #define ll long long
  #define mod 998244353
  #define eps 1e-7
  using namespace std;
  
  const double PI = acos(-1);
  const int INF = 0x3f3f3f3f;
  const int N = 5e2 + 10;
  
  void solve()
  {
  	ll n, m;
  	cin >> n >> m;
  	vector<ll> a(n), cnt(m + 10); // cnt[x]表示长度为x的胡萝卜有几个
  	ll sum_a = 0;
  	for (ll i = 0; i < n; i++)
  	{
  		cin >> a[i];
  		sum_a += a[i];
  		cnt[a[i]]++;
  	}
  
  	vector<ll> s(m + 10);
  	for (ll i = 1; i <= m; i++)
  	{
  		s[i] = s[i - 1] + cnt[i];
  	}
  
  	vector<ll> sumj(m + 10), ans(20);
  	ll maxk = min(m, 17ll);
  
  	for (ll v = 1; v <= m; v++)
  	{
  		// 倍数枚举 v=3 [0,1,2] [3,4,5]...
  		//[v*j, v*(j+1)-1] -> floor(L/v)==j
  		ll maxj = m / v;
  		for (ll j = 1; j <= maxj; j++)
  		{
  			ll L = v * j;
  			ll R = min(m, v * (j + 1) - 1);
  			ll num = s[R] - s[L - 1];
  			sumj[j] = sumj[j - 1] + num * j;
  		}
  
  		for (ll k = 1; k <= maxk; k++)
  		{
  			ll limit = (1 << k) - 1;
  			ll tmp = 0;
  
  			if (limit >= maxj) // 当前所有的段都是v
  			{
  				tmp = sumj[maxj];
  			}
  			else // limit<maxj
  			{
  				tmp = sumj[limit];
  				ll val = (limit + 1) * v;
  				if (val <= m)
  				{
  					tmp += cnt[val] * (limit + 1) + (s[m] - s[val]) * limit;
  				}
  			}
  			ans[k] = max(ans[k], tmp);
  		}
  	}
  	for (ll k = 1; k <= m; k++)
  	{
  		if (k <= 17)
  			cout << ans[k] << " ";
  		else
  			cout << sum_a << " ";
  	}
  	cout << "\n";
  }
  int main()
  {
  	// ios_base::sync_with_stdio(false);
  	// cin.tie(nullptr);
  	int t = 1;
  	cin >> t;
  	while (t--)
  	{
  		solve();
  	}
  
  	return 0;
  }
  
  /*
  我们现在关注对某一根长度为 L 的胡萝卜，如果把它切成长度为 v 的段，最多切成多少段？
  floor(L/v)
  
  如果我们对某一根长度为L的胡萝卜，切 k 次，能够得到多少长度为 v 的段？O(mlogm*min(m,17)) 只有 k =1,2,...,17才需要精确计算和枚举
  
  floor(L/v) 去和 2^k 比较
  
  floor(L/v)<2^k-1 -> floor(L/v)
  
  floor(L/v)==2^k-1 -> 2^k+1
  floor(L/v)>2^k-1->2^k-1
  
  v=1, v=2, v=3,..., v=m
  调和级数的枚举
  
  k大到一定的数字的时候，就不需要算了，一定是都切成长度为1
  */