ICPC 2021 上海區域賽 F Kaiji!

題意

有一個序列 a，從小到大排序。Alice 每次在 a 中選擇兩個相鄰的值，分別放到 Bob 的左右手。Bob 可以選擇左手或者右手，然後 Alice 將會告訴 Bob 所選擇的手上的值。最後 Bob 需要猜測左右手上球的大小關係。問 Bob 能獲得的最大勝率 p，使得對於 Alice 的所有可能選擇，Bob 獲勝的機率都不小於 p。

解析

a 的具體值實際上不重要，可以先離散化。

首先，在 Bob 選擇左右手這個環節，一定是左右手各一半機率，否則若 Alice 在 Bob 更大機率選到的手上放了較難的值，則獲勝機率會變低。

然後就是 Bob 需要對每一個可能選到的值 i，確定 $f_{i}$，$g_{i}$，$h_{i}$，分別表示拿到 i 之後猜測已知值小於，等於和大於位置值的機率。滿足 $f_{i}+g_{i}+h_{i} =1$。

考慮 $g_{i}$。為了方便，令 $t_{i}$ 表示值 i 是否出現了多於 1 次。假設答案為 w，一個顯然的關係是：$g_{i} \ge t_{i}w$，即如果 i 只出現了一次，那麼關係不可能是相等，否則，猜測 $g_{i}$ 的機率至少要為 w。不妨就讓 $g_{i} = w$。然後假設雙手的值分別是 i 和 i+1，則也要滿足 $\frac{f_{i}+h_{i+1}}{2} \ge w$，即已知 i 猜小於和已知 i+1 猜大於的機率的平均值要不小於 w。整理一下可以得到 $f_{i+1} \le f_{i} +1-t_{i+1}w-2w$。同時注意到 $0 \le f_{i} \le 1 - t_{i}w$，故有：$0 \le f_{i+1} \le \min\{1 - t_{i+1}w, f_{i}+1-(t_{i+1}+2)w\}$

容易發現，$f_{i}$ 的上界由 $t_{i}$ 和 $f_{i-1}$ 決定，且最大化 $f_{i-1}$ 不會讓 $f_{i}$ 上界變小，所以我們不妨就令：

$$f_{i+1}=\min\{\textcolor{red}{1 - t_{i+1}w}, \textcolor{blue}{f_{i}+1-(t_{i+1}+2)w}\}$$

問題在於 w 並沒有被確定。考慮繼續簡化這個轉移。由於紅色轉移和之前的 f 都是沒有關係的，所以 $f_{i}$ 一定是從某一個 $f_{j}$ 用了紅色轉移，然後從 $j$ 到 $i$ 都用藍色轉移得到的最小值，可以推出式子（令 $s_{i}=\sum_{j=0}^{i} t_{j}$）：

$$\begin{aligned} f_{i} &= \textcolor{red}{1-t_{j}w}+\textcolor{blue}{(i-j)-[s_{i}-s_{j}+2(i-j)w]} \\ &= (i-j+1)-[s_{i}-s_{j-1}+2(i-j)w] \end{aligned}$$

轉化一下可以得到 w 的限制：

$$w \le \frac{i - j + 1}{s_{i}-s_{j-1}+2(i-j)}$$

故就是要求右邊那個分式的最小值。可以看作是點 $(s_{i} + 2i, i+1)$ 到所有 $(s_{j-1} + 2j, j)$ 的斜率最小值（$i \le j$）。維護一個上凸包，由於 $(s_{j-1} +2j)$ 單調遞增，可以用單調棧維護。然後在凸包上二分即可。時間複雜度 $O(n\log n)$，但實際上這個凸包大小不會太大，所以容易通過。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

void set_io(std::string name)
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

constexpr int P = 998'244'353;

constexpr long long pow_mod(long long x, long long y)
{
  y %= P - 1;
  x %= P;
  long long r = 1;
  while (y) {
    if (y & 1) r = r * x % P;
    x = x * x % P;
    y >>= 1;
  }
  return r;
}

constexpr long long inv(long long x) { return pow_mod(x, P - 2); }

struct vec_t
{
  int x, y;
  vec_t() : x(0), y(0) {}
  vec_t(int x, int y) : x(x), y(y) {}
  vec_t &operator+=(const vec_t &v) 
  {
    x += v.x;
    y += v.y;
    return *this;
  }
  vec_t &operator-=(const vec_t &v) 
  {
    x -= v.x;
    y -= v.y;
    return *this;
  }
  vec_t operator+(const vec_t &v) const { return vec_t(*this) += v; }
  vec_t operator-(const vec_t &v) const { return vec_t(*this) -= v; }

#define slope_compare(op)                                  \
  friend bool operator op (const vec_t &a, const vec_t &b) \
  {                                                        \
    return (long long)b.x * a.y op (long long)a.x * b.y;   \
  }
  slope_compare(<)
  slope_compare(>)
  slope_compare(<=)
  slope_compare(>=)
#undef slope_compare
};

void solve()
{
  int n, a, A, B, C, M;
  std::cin >> n >> a >> A >> B >> C >> M;
  A %= M;
  B %= M;
  C %= M;
  a %= M;
  std::vector<int> cnt(M);
  for (int i = 1; i <= n; i++) {
    a = (((long long)A * a % M * a % M + (long long)B * a % M) % M + C) % M + 1;
    cnt[a - 1]++;
  }

  std::vector<vec_t> st;
  vec_t ans(1, 1);
  int s = 0;

  auto insert = [&st](const vec_t &p)
  {
    while (st.size() >= 2 && (st.end()[-1] - st.end()[-2]) <= (p - st.end()[-1])) st.pop_back();
    st.emplace_back(p);
  };
  auto find = [&st](const vec_t &p) 
  {
    int l = 0, r = st.size() - 1;
    while (l < r) {
      int mid = l + (r - l) / 2;
      if (st[mid + 1] - st[mid] < p - st[mid]) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return st[r];
  };

  int j = 0;
  for (int i = 0; i < M; i++) {
    if (cnt[i] == 0) continue;
    int t = cnt[i] >= 2;
    insert(vec_t(s + 2 * j, j));
    vec_t p(s + t + 2 * j, j + 1);
    auto q = find(p);
    auto d = p - q;
    if (d < ans) ans = d;
    s += t;
    j++;
  }

  std::cout << (long long)ans.y * inv(ans.x) % P << std::endl;
}

int main()
{
  set_io("game");

  int t;
  std::cin >> t;
  while (t--) solve();
}