2026 Autumn Training · 做题记录

CF1187F. Expected Square Beauty [done]

题意独立均匀取整数 $𝑋_{𝑖} \in [𝑙_{𝑖}, 𝑟_{𝑖}]$ ，求极大连续相等段数的平方期望。

数据范围 $1 \leq 𝑛 \leq 2 \times 10^{5}$ ， $1 \leq 𝑙_{𝑖} \leq 𝑟_{𝑖} \leq 10^{9}$ 。

Solution

考虑计算 $𝐸 [𝐵^{𝑘}]$ ，其中 $𝑘 \geq 1$ ，原题对应 $𝑘 = 2$ 。下标从 $0$ 开始，取值区间转为 $[𝐿_{𝑖}, 𝑅_{𝑖})$ ，末尾补充哨兵区间 $[0, 1)$ 。记此时共有 $𝑁$ 个变量、 $𝑚 = 𝑁 - 1$ 条边， ${il}_{𝑖} = {(𝑅_{𝑖} - 𝐿_{𝑖})}^{- 1}$ 。令 $𝑌_{𝑖} = [𝑋_{𝑖} \neq 𝑋_{𝑖 + 1}]$ ，则段数 $𝐵 = \sum_{𝑖 = 0}^{𝑚 - 1} 𝑌_{𝑖}$ 。

展开 $𝐵^{𝑘}$ 时，每项至多涉及 $𝑘$ 条不同的边，而总边数为 $𝑚$ ，故只需统计 $𝑗 \leq 𝑞 = min (𝑘, 𝑚)$ 条边的贡献。每个选中连续段的长度不超过总选边数 $𝑗$ ，因此连续段长度也只需计算到 $𝑞$ 。

先求 $𝑤_{𝑙, 𝑡}$ ，表示边段 $[𝑙, 𝑙 + 𝑡)$ 全部满足 $𝑌_{𝑖} = 1$ 的概率。

连续段概率的容斥

变量区间 $[𝑠, 𝑟)$ 全部相等的概率为

𝑐 (𝑠, 𝑟) = max (0, min_{𝑠 \leq 𝑖 < 𝑟} 𝑅_{𝑖} - max_{𝑠 \leq 𝑖 < 𝑟} 𝐿_{𝑖}) \prod_{𝑖 = 𝑠}^{𝑟 - 1} {il}_{𝑖} .

令 $𝑟 = 𝑙 + 𝑡 + 1$ 。在相等事件的容斥展开中，按包含 $𝑋_{𝑟 - 1}$ 的连通块 $[𝑠, 𝑟)$ 分类。块内 $𝑟 - 𝑠 - 1$ 条边均选入容斥集合；若 $𝑠 > 𝑙$ ，分隔边 $𝑠 - 1$ 未选。因此

𝑤_{𝑙, 𝑡} = \sum_{𝑠 = 𝑙}^{𝑟 - 1} {(- 1)}^{𝑟 - 𝑠 - 1} 𝑐 (𝑠, 𝑟) {\begin{cases} 1 & 𝑠 = 𝑙 \\ 𝑤_{𝑙, 𝑠 - 𝑙 - 1} & 𝑠 > 𝑙 \end{cases} .

初值 $𝑤_{𝑙, 0} = 1$ 。未选入容斥集合的边不施加相等约束。

按 $𝑡$ 递增计算，固定 $𝑟$ 后向左枚举 $𝑠$ ，维护区间交集与逆元乘积，即可常数时间更新 $𝑐 (𝑠, 𝑟)$ 。

再求 ${dp}_{𝑖, 𝑗}$ ，表示边前缀 $[0, 𝑖)$ 中所有大小为 $𝑗$ 的边集同时变化的概率之和。将选中的边分解为极大连续段，不同段之间至少空出一条边，依赖的原变量集合不交，因此联合概率为各段概率之积。

DP 转移

按末边是否被选分类。若被选，枚举最后一个极大连续段的长度 $𝑡$ ，其前一条边必须未选：

{dp}_{𝑖, 𝑗} = {dp}_{𝑖 - 1, 𝑗} + \sum_{𝑡 = 1}^{min (𝑖, 𝑗)} 𝑤_{𝑖 - 𝑡, 𝑡} {\begin{cases} [𝑗 = 𝑡] & 𝑖 = 𝑡 \\ {dp}_{𝑖 - 𝑡 - 1, 𝑗 - 𝑡} & 𝑖 > 𝑡 \end{cases} .

初值 ${dp}_{0, 0} = 1$ ，其余状态为 $0$ 。

令 $𝑎_{𝑗} = {dp}_{𝑚, 𝑗} = 𝐸 [(\binom{𝐵}{𝑗})]$ 。指示变量的重复幂可以合并，按不同下标的数量分组，用第二类 Stirling 数还原：

𝐸 [𝐵^{𝑘}] = \sum_{𝑗 = 0}^{𝑞} 𝑆 (𝑘, 𝑗) 𝑗! 𝑎_{𝑗} .

其中 $𝑆 (𝑘, 𝑗) = 𝑆 (𝑘 - 1, 𝑗 - 1) + 𝑗 𝑆 (𝑘 - 1, 𝑗)$ ， $𝑆 (0, 0) = 1$ ，其余边界状态为 $0$ 。代码用 $𝑠_{𝑗}$ 倒序滚动计算，最后得到 $𝑠_{𝑗} = 𝑆 (𝑘, 𝑗)$ 。

总时间为 $𝑂 (𝑚 𝑞^{2} + 𝑘 𝑞)$ ，空间为 $𝑂 (𝑚 𝑞)$ 。原题 $𝑘 = 2$ 时为线性规模。

C++

#include "noya/head.hpp"

#include "noya/modint.hpp"

using namespace noya;

using mi = mint107;

vc<vc<mi>> block_probabilities(const vl &L, const vl &R, int k) {
  int N = sz(L), m = N - 1, q = min(k, m);
  vc<mi> il(N);
  rep(i, N) il[i] = mi(R[i] - L[i]).inv();

  vc<vc<mi>> w(m, vc<mi>(q + 1));
  rep(l, m) {
    w[l][0] = 1;
    rep(t, 1, min(q, m - l) + 1) {
      int r = l + t + 1;
      ll ml = L[r - 1], mr = R[r - 1];
      mi prod = 1;
      for (int s = r - 1; s >= l; s--) {
        cmax(ml, L[s]);
        cmin(mr, R[s]);
        prod *= il[s];
        mi c = mi(max(mr - ml, ll(0))) * prod;
        mi pre = s == l ? mi(1) : w[l][s - l - 1];
        if ((r - s - 1) & 1)
          w[l][t] -= pre * c;
        else
          w[l][t] += pre * c;
      }
    }
  }
  return w;
}

vc<mi> factorial_moments(const vc<vc<mi>> &w, int k) {
  int m = sz(w), q = min(k, m);
  vc<vc<mi>> dp(m + 1, vc<mi>(q + 1));
  dp[0][0] = 1;
  rep(i, 1, m + 1) {
    dp[i] = dp[i - 1];
    rep(j, 1, min(i, q) + 1) {
      rep(t, 1, min(i, j) + 1) {
        int l = i - t;
        mi pre = l == 0 ? mi(j == t) : dp[l - 1][j - t];
        dp[i][j] += pre * w[l][t];
      }
    }
  }
  return dp[m];
}

mi expected_moment(const vl &L, const vl &R, int k) {
  assert(k >= 0 && !L.empty() && sz(L) == sz(R));
  auto w = block_probabilities(L, R, k);
  auto a = factorial_moments(w, k);
  int q = sz(a) - 1;
  vc<mi> s(q + 1);
  s[0] = 1;
  rep(n, k) {
    for (int j = min(n + 1, q); j > 0; j--) {
      s[j] = s[j - 1] + mi(j) * s[j];
    }
    s[0] = 0;
  }
  mi fac = 1, ans = s[0] * a[0];
  rep(j, 1, q + 1) {
    fac *= j;
    ans += s[j] * fac * a[j];
  }
  return ans;
}

void solve(int k = 2) {
  int n;
  cin >> n;
  vl L(n), R(n);
  rep(i, n) cin >> L[i];
  rep(i, n) {
    cin >> R[i];
    R[i]++;
  }
  L.push_back(0);
  R.push_back(1);

  cout << expected_moment(L, R, k).val() << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

ABC476G. Increasing Popcount [done]

题意将 $popcount (𝐿), \dots, popcount (𝑅)$ 划分成尽量少的严格递增子序列，求最少个数。

数据范围 $1 \leq 𝑇 \leq 10^{4}$ ， $1 \leq 𝐿 \leq 𝑅 \leq 10^{18}$ 。

Solution

由 Dilworth 定理，答案等于 popcount 序列的最长不升子序列长度，相等值可以连续选取。

令 $𝐵 = 60$ ，将输入区间转为 $[𝐿, 𝑅)$ 。按照线段树查询的方式，从左到右拆成 $𝑂 (𝐵)$ 个二进制对齐块。每次取不越过 $𝑅$ 、且 $𝐿$ 为其长度倍数的最大块 $[𝐿, 𝐿 + 2^{𝑘})$ 。令 $𝑐 = popcount (𝐿)$ ，块内值为 $𝑐 + popcount (𝑥)$ ，其中 $0 \leq 𝑥 < 2^{𝑘}$ ；值 $𝑐 + 𝑡$ 出现 $𝐶_{𝑘, 𝑡} = (\binom{𝑘}{𝑡})$ 次。

块内只需考虑选取某个固定的 popcount 值。对于任意非空不升子序列，都能在其最小值与最大值之间找到一层，改选该层的全部元素，长度不减，且仍能与两侧拼接。

为什么块内只需选择一个值

忽略共同的高位贡献 $𝑐$ ，对 $𝑘$ 归纳。 $𝑘 = 0$ 时结论显然成立。对于 $𝑘 > 0$ ，将块均分为左右两半，右半的 popcount 比左半对应位置多 $1$ 。对非空的半块子序列应用归纳假设，可替换为该半块中某一值的全部元素，长度不减，且替换值仍在原子序列的值域内。

若只选了一半，直接在整块中选取同一个值，数量不会减少。否则，设左半选值 $𝑎$ ，右半选值 $𝑏$ ，必有 $𝑎 \geq 𝑏$ ，两半的数量分别为 $𝐶_{𝑘 - 1, 𝑎}$ 和 $𝐶_{𝑘 - 1, 𝑏 - 1}$ 。

令 $ℎ = ⌊ \frac{𝑘 - 1}{2} ⌋$ 。由二项式系数的单峰性，当 $𝑎 > 𝑏$ 时，可以进行以下调整：

若 $𝑎 > ℎ$ ，则 $𝐶_{𝑘 - 1, 𝑎 - 1} \geq 𝐶_{𝑘 - 1, 𝑎}$ ，将左半所选值由 $𝑎$ 改为 $𝑎 - 1$ 。
若 $𝑎 \leq ℎ$ ，则 $𝑏 < 𝑎 \leq ℎ$ ，从而 $𝐶_{𝑘 - 1, 𝑏} \geq 𝐶_{𝑘 - 1, 𝑏 - 1}$ ，将右半所选值由 $𝑏$ 改为 $𝑏 + 1$ 。

每次调整后仍选取相应值的全部元素，所选数量不减，且仍有 $𝑎 \geq 𝑏$ 。同时，非负整数 $𝑎 - 𝑏$ 减少 $1$ ，因此有限次调整后必有 $𝑎 = 𝑏$ 。

最终二者相等，记为 $𝑣$ ，此时选中的正是整个块中值为 $𝑣$ 的一层，其大小为

𝐶_{𝑘 - 1, 𝑣} + 𝐶_{𝑘 - 1, 𝑣 - 1} = 𝐶_{𝑘, 𝑣} .

所有调整后的值均落在初始的 $[𝑏, 𝑎]$ 内，因而仍在原子序列的值域内，不影响与块外两侧拼接，归纳完成。

令 ${dp}_{𝑗}$ 为已处理前缀中末项至少为 $𝑗$ 的最长不升子序列长度，初值均为 $0$ ，表示空序列。追加一块时，选取值为 $𝑗$ 的整层，贡献为 $𝐶_{𝑘, 𝑗 - 𝑐}$ ；再对末值取后缀最大值。按 $𝑗 = 𝑐 + 𝑘, \dots, 0$ 逆序更新：

{dp}_{𝑗} \leftarrow max ({dp}_{𝑗} + 𝐶_{𝑘, 𝑗 - 𝑐}, {dp}_{𝑗 + 1}) .

其中 $𝑡 < 0$ 或 $𝑡 > 𝑘$ 时 $𝐶_{𝑘, 𝑡} = 0$ 。更新时 ${dp}_{𝑗}$ 仍是旧状态， ${dp}_{𝑗 + 1}$ 已是新状态，可直接原地转移。最终答案为 ${dp}_{0}$ 。

预处理二项式系数需 $𝑂 (𝐵^{2})$ 时间与空间；每组需 $𝑂 (𝐵^{2})$ 时间、 $𝑂 (𝐵)$ 额外空间。

C++

#include "noya/head.hpp"

#include <bit>

using namespace noya;

constexpr int B = 60;
ll C[B + 1][B + 1];

void solve() {
  ll L, R;
  cin >> L >> R;
  R++;
  ll dp[B + 2]{};
  while (L < R) {
    int k = min(countr_zero(ull(L)), int(bit_width(ull(R - L))) - 1);
    int c = popcount(ull(L));
    for (int j = c + k; j >= 0; j--) {
      if (j >= c) dp[j] += C[k][j - c];
      cmax(dp[j], dp[j + 1]);
    }
    L += 1LL << k;
  }
  cout << dp[0] << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  rep(k, B + 1) {
    C[k][0] = 1;
    rep(j, 1, k + 1) C[k][j] = C[k - 1][j - 1] + C[k - 1][j];
  }
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

CF1187F. Expected Square Beauty [done]

Solution

ABC476G. Increasing Popcount [done]

Solution

Comments