結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー NyaanNyaan
提出日時 2025-12-23 23:55:18
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 5,532 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 258 ms
コンパイル使用メモリ 8,104 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-23 23:55:19
合計ジャッジ時間 1,554 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// bagutteru ue ni osoi...

#include "template/template.hpp"
//
#include "math/stern-brocot-tree.hpp"
//
#include "modint/montgomery-modint.hpp"
#include "modulo/binomial.hpp"
//
using namespace Nyaan;
using mint = LazyMontgomeryModInt<998244353>;
// using mint = LazyMontgomeryModInt<1000000007>;
using vm = vector<mint>;
using vvm = vector<vm>;

mint naive(ll N) {
  mint ans = 0;
  rep1(H, N) {
    ll x = (2 * N + 1) / (2 * H + 1);
    if (x < 3) break;
    ans += (x - 1) / 2;
  }
  return ans;
}

mint calc(ll N) {
  // (-2x+1)(2y+1)>=2N+2
  auto inside = [&](i128 x, i128 y) -> bool {
    return (-2 * x + 1) * (2 * y + 1) >= 2 * N + 2;
  };

  i128 xl = -(N + 1), yl = 0, xr = 0;

  /*
  auto candicate = [&](i128 x, i128 y, i128 c, i128 d)  {
    i128 a = x * d - y * c;
    // (-2x+1)(2y+1)=2N+2
    // xd-yc=a
    // (-2x+1)(2yc+c)=c(2N+2)
    // (-2x+1)(2(xd-a)+c)=c(2N+2)
    // (-2x+1)(2dx+(c-2a))=c(2N+2)
    i128 A = -2 * 2 * d;
    i128 B = -2 * (c - 2 * a) + 2 * d;
    long double x_dst = -1.0l * B / (2 * A);
    i128 res = max<i128>(1, (x_dst - x) / c + 0.5);
    trc(x, y, c, d, res);
    return res;
  };
  */

  using Int = i128;
  vector<pair<Int, Int>> cv;
  {
    using ld = long double;
    // inside かつ x <= xr
    auto f = [&](Int x, Int y) { return x <= xr && inside(x, y); };

    // (a, b) から (c, d) 方向に進めるだけ進む
    auto go_naive = [&](Int a, Int b, Int c, Int d) -> Int {
      assert(f(a, b));
      Int r = 1, s = 0;
      while (f(a + r * c, b + r * d)) r *= 2;
      while ((r /= 2) != 0) {
        if (f(a + r * c, b + r * d)) s += r, a += r * c, b += r * d;
      }
      return s;
    };

    auto go = [&](Int a, Int b, Int c, Int d) -> Int {
      assert(f(a, b));
      // trc("go1", a, b, c, d);
      if (c == 0) {
        assert(d == -1);
        assert(!f(a + c, b + d));
        return 0;
      }
      i128 rhs = a * d - b * c;
      // (-2x+1)(2y+1)=2N+2
      // xd-yc=r
      // (-2x+1)(2yc+c)=c(2N+2)
      // (-2x+1)(2(xd-r)+c)=c(2N+2)
      // (-2x+1)(2dx+(c-2r))=c(2N+2)
      i128 A = -2 * 2 * d;
      i128 B = -2 * (c - 2 * rhs) + 2 * d;
      i128 C = c - 2 * rhs - c * (2 * N + 2);
      ld sqrtD = sqrtl(ld(B) * B - 4.0l * A * C);
      if (isnan(sqrtD)) sqrtD = 0;
      if (A == 0) trc(a, b, c, d, A, B, C);
      ld x1 = A != 0 ? (-B - sqrtD) / (2 * A) : -1.0l * C / B;
      i128 s = max<i128>(0, (min<ld>(xr, x1) - a) / c + 0.5l);
      trc(s);
      while (!f(a + s * c, b + s * d)) s--;
      while (f(a + (s + 1) * c, b + (s + 1) * d)) s++;
      trc("go1", a, b, c, d, s);
      assert(go_naive(a, b, c, d) == s);
      return s;
    };
    // (a, b) が out, (a + c * k, b + d * k) が in とする
    // out の間進めるだけ進む
    // 無限に進めるときは -1
    auto go2 = [&](Int a, Int b, Int c, Int d) -> Int {
      assert(!f(a, b) and !f(a + c, b + d));
      if (c == 0) {
        assert(d == 1);
        // (-2x+1)(2y+1)=2N+2
        Int q = ((2 * N + 2) / (-2 * a + 1) - 1) / 2;
        while ((-2 * a + 1) * (2 * q + 1) < 2 * N + 2) q++;
        trc("go2", a, b, c, d, q);
        return (q - b) - 1;
      }
      i128 rhs = a * d - b * c;
      // (-2x+1)(2y+1)=2N+2
      // xd-yc=a
      // (-2x+1)(2yc+c)=c(2N+2)
      // (-2x+1)(2(xd-a)+c)=c(2N+2)
      // (-2x+1)(2dx+(c-2a))=c(2N+2)
      i128 A = -2 * 2 * d;
      i128 B = -2 * (c - 2 * rhs) + 2 * d;
      i128 C = c - 2 * rhs - c * (2 * N + 2);
      ld sqrtD = sqrtl(ld(B) * B - 4.0l * A * C);
      if (isnan(sqrtD)) sqrtD = 0;
      ld x0 = A == 0 ? (-B + sqrtD) / (2 * A) : -C / B;
      i128 s = max<i128>(0, (min<i128>(xr, x0) - a) / c + 0.5l);
      trc("go2", a, b, c, d, s);
      if (s - 1 > 0 and !f(a + (s - 1) * c, b + (s - 1) * d)) return s - 2;
      if (s - 0 > 0 and !f(a + (s - 0) * c, b + (s - 0) * d)) return s - 1;
      if (s + 1 > 0 and !f(a + (s + 1) * c, b + (s + 1) * d)) return s - 0;
      if (s + 2 > 0 and !f(a + (s + 2) * c, b + (s + 2) * d)) return s + 1;
      if (s + 3 > 0 and !f(a + (s + 3) * c, b + (s + 3) * d)) return s + 2;
      return -1;
    };

    Int x = xl, y = yl;
    assert(f(x, y) and go(x, y, 0, -1) == 0);
    cv.emplace_back(x, y);
    SternBrocotTreeNode<Int> sb;
    while (x < xr) {
      Int a, b;
      if (f(x + 1, y)) {
        a = 1, b = 0;
      } else {
        while (!f(x + sb.lx, y + sb.ly)) {
          assert(!sb.seq.empty());
          Int bc = sb.seq.back();
          sb.go_parent(bc < 0 ? -bc : bc);
        }
        while (true) {
          assert(f(x + sb.lx, y + sb.ly));
          assert(!f(x + sb.rx, y + sb.ry));
          if (f(x + sb.lx + sb.rx, y + sb.ly + sb.ry)) {
            Int s = go(x + sb.lx, y + sb.ly, sb.rx, sb.ry);
            assert(s > 0);
            sb.go_right(s);
          } else {
            Int t = go2(x + sb.rx, y + sb.ry, sb.lx, sb.ly);
            if (t <= 0) {
              a = sb.lx, b = sb.ly;
              break;
            } else {
              sb.go_left(t);
            }
          }
        }
      }
      Int s = go(x, y, a, b);
      x += a * s, y += b * s;
      cv.emplace_back(x, y);
    }
  }

  mint ans = 0;
  Binomial<mint> C;
  rep(i, sz(cv) - 1) {
    ll y = cv[i].se;
    ll dx = cv[i + 1].fi - cv[i].fi;
    ll dy = cv[i + 1].se - cv[i].se;
    ll g = gcd(dx, dy);
    mint cur = (mint{dx + 1} * (dy + 1) - (g + 1)) * C.inv(2) - dx - dy;
    cur += mint{dx} * y;
    ans += cur;
  }
  return ans + 1;
}

void q() {
  inl(N);
  out(calc(N));
}

void Nyaan::solve() {
  int t = 1;
  in(t);
  while (t--) q();
}
0