結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー Kude
提出日時 2025-12-26 23:46:11
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 2,798 ms / 3,000 ms
コード長 4,264 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,309 ms
コンパイル使用メモリ 288,512 KB
実行使用メモリ 70,452 KB
最終ジャッジ日時 2025-12-26 23:46:57
合計ジャッジ時間 46,148 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

struct Vc {
  ll x, y;
  friend Vc operator+(const Vc& lhs, const Vc& rhs) {
    return {lhs.x + rhs.x, lhs.y + rhs.y};
  }
  friend Vc operator*(ll a, const Vc& v) { return {a * v.x, a * v.y}; }
};
struct S {
  Vc inCand, out;
};
void lattice_hull(Vc start, vector<S> sbtree, auto op, auto is_inside, auto get_t_cand, int t_margin = 0) {
  auto find_max_true = [](auto pred) {
    // l = 0 -> true
    ll l = 0, r = 1;
    while (pred(r)) l = r, r *= 2;
    while (r - l > 1) {
      auto c = midpoint(l, r);
      (pred(c) ? l : r) = c;
    }
    return l;
  };
  auto find_min_true = [](auto pred, ll ub) {
    // l = 0 -> false
    // search in [1, ub]
    ll l = 0, r = 1;
    while (!pred(r)) {
      if (r == ub) return -1LL;
      l = r, r = min(2 * r, ub);
    }
    while (r - l > 1) {
      auto c = midpoint(l, r);
      (pred(c) ? r : l) = c;
    }
    return r;
  };
  auto v = start;
  while (true) {
    while (!sbtree.empty() && !is_inside(v + sbtree.back().inCand)) {
      sbtree.pop_back();
    }
    if (sbtree.empty()) break;
    bool now_inside = is_inside(v + sbtree.back().inCand + sbtree.back().out);
    while (true) {
      auto [vin, vout] = sbtree.back();
      if (now_inside) {
        ll t = find_max_true(
            [&](ll t) { return is_inside(v + vin + (t + 1) * vout); });
        sbtree.emplace_back(vin + (t + 1) * vout, vout);
        now_inside = false;
      } else {
        ll ub = get_t_cand(v + vin + vout, vin);
        auto pred = [&](ll t) {
          // v + (t+1)vin + vout
          ll x, y;
          if (__builtin_mul_overflow(t + 1, vin.x, &x) ||
              __builtin_mul_overflow(t + 1, vin.y, &y) ||
              __builtin_add_overflow(x, v.x + vout.x, &x) ||
              __builtin_add_overflow(y, v.y + vout.y, &y))
            return false;
          return is_inside(Vc{x, y});
        };
        ll t = ub >= 1 ? find_min_true(pred, ub) : -1LL;
        if (t == -1) {
          for (int dt = 1; dt <= t_margin; dt++) {
            if (ub + dt >= 1 && pred(ub + dt)) {
              t = ub + dt;
              break;
            }
          }
          if (t == -1) break;
        }
        sbtree.emplace_back(vin, t * vin + vout);
        now_inside = true;
      }
    }
    auto w = sbtree.back().inCand;
    ll t = find_max_true([&](ll t) { return is_inside(v + (t + 1) * w); }) + 1;
    op(v, v + t * w, t);
    v = v + t * w;
  }
}

auto floor_div(signed_integral auto x, signed_integral auto y) {
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
auto ceil_div(signed_integral auto x, signed_integral auto y) {
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}

mint solve(ll n) {
  // x(y+1)+y(x+1) > n
  // (2x+1)(2y+1) > 2n+1

  // (2x+1)^2 <= 2n+1
  // <=> x <= (sqrt(2n+1)-1)/2
  ll c = ((ll)sqrtl(2 * n + 1) - 1) / 2;
  Vc start{c + 1, (c + 2 + n) / (2 * c + 3)};
  mint ans;
  ans += start.y - 1;
  const mint inv2 = mint(2).inv();
  auto op = [&](Vc u, Vc v, ll t) {
    ll dx = v.x - u.x, dy = u.y - v.y;
    ans += mint(dx) * u.y - (mint(dx + 1) * (dy + 1) + t - 1) * inv2;
  };
  auto is_inside = [&](Vc v) {
    ll z;
    return v.x <= n && 0 < v.y && v.y <= n &&
           !__builtin_mul_overflow(2 * v.x + 1, 2 * v.y + 1, &z) &&
           z > 2 * n + 1;
  };
  auto get_t_cand = [&](Vc p, Vc v) {
    ll t;
    if (v.y == 0) {
      // (2(px+t)+1)(2py+1) > 2n+1
      t = (floor_div(2 * n + 1, 2 * p.y + 1) - 1) / 2 - p.x;
    } else {
      // (2(px+tvx)+1)(2(py+tvy)+1) > 2n+1
      // t = (-px-1/2)/vx = (-2px-1)/2vx
      t = floor_div(
          floor_div(-2 * p.x - 1, 2 * v.x) + floor_div(-2 * p.y - 1, 2 * v.y),
          2);
    }
    ll nx;
    if (t > 1 && (__builtin_mul_overflow(v.x, t, &nx) ||
                  __builtin_add_overflow(nx, p.x, &nx) || nx > n)) {
      // px + tvx <= n
      t = (n - p.x) / v.x;
    }
    return t;
  };
  lattice_hull(start, {{1, 0, 0, -1}}, op, is_inside, get_t_cand, 1);
  ans = 2 * ans + mint(c).pow(2);
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    ll n;
    cin >> n;
    cout << solve(n).val() << '\n';
  }
}
0