ICPC 2021 上海区域赛 F Kaiji!

標籤: icpcmathdp

题意

有一个序列 a,从小到大排序。Alice 每次在 a 中选择两个相邻的值,分别放到 Bob 的左右手。Bob 可以选择左手或者右手,然后 Alice 将会告诉 Bob 所选择的手上的值。最后 Bob 需要猜测左右手上球的大小关系。问 Bob 能获得的最大胜率 p,使得对于 Alice 的所有可能选择,Bob 获胜的概率都不小于 p。

解析

a 的具体值实际上不重要,可以先离散化。

首先,在 Bob 选择左右手这个环节,一定是左右手各一半概率,否则若 Alice 在 Bob 更大概率选到的手上放了较难的值,则获胜概率会变低。

然后就是 Bob 需要对每一个可能选到的值 i,确定 ,分别表示拿到 i 之后猜测已知值小于,等于和大于位置值的概率。满足

考虑 。为了方便,令 表示值 i 是否出现了多于 1 次。假设答案为 w,一个显然的关系是:,即如果 i 只出现了一次,那么关系不可能是相等,否则,猜测 的概率至少要为 w。不妨就让 。然后假设双手的值分别是 i 和 i+1,则也要满足 ,即已知 i 猜小于和已知 i+1 猜大于的概率的平均值要不小于 w。整理一下可以得到 。同时注意到 ,故有:

容易发现, 的上界由 决定,且最大化 不会让 上界变小,所以我们不妨就令:

问题在于 w 并没有被确定。考虑继续简化这个转移。由于红色转移和之前的 f 都是没有关系的,所以 一定是从某一个 用了红色转移,然后从 都用蓝色转移得到的最小值,可以推出式子(令 ):

转化一下可以得到 w 的限制:

故就是要求右边那个分式的最小值。可以看作是点 到所有 的斜率最小值()。维护一个上凸包,由于 单调递增,可以用单调栈维护。然后在凸包上二分即可。时间复杂度 ,但实际上这个凸包大小不会太大,所以容易通过。

#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();
}