結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー svel gr
提出日時 2026-01-05 14:11:02
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,613 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,207 ms
コンパイル使用メモリ 116,144 KB
実行使用メモリ 19,536 KB
最終ジャッジ日時 2026-01-05 14:11:12
合計ジャッジ時間 9,928 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef __int128 i128;

const ll MOD = 998244353;

// 2hw + h + w > n
// i128 で計算
inline bool is_outside(ll h, ll w, ll n) {
    if (h < 0 || w < 0) return true;
    return (i128)h * (2 * w + 1) + w > n;
}

// Stern-Brocot
inline bool slope_steeper(ll h, ll w, ll dh, ll dw) {
    return (i128)(w * 2 + 1) * dh <= (i128)(h * 2 + 1) * dw;
}

void solve() {
    ll n;
    if (!(cin >> n)) return;

    // h=w
    ll border = sqrt(n / 2.0);
    while ((i128)2 * (border + 1) * (border + 1) + 2 * (border + 1) <= n) border++;
    while ((i128)2 * border * border + 2 * border > n) border--;

    if (border < 1) {
        cout << 0 << "\n";
        return;
    }

    ll h = border + 1;
    ll w = (n - h) / (2 * h + 1);
    while (is_outside(h, w, n)) w++;

    i128 ret = 0;
    stack<pair<ll, ll> > sbt;
    sbt.push(make_pair(0LL, 1LL));
    sbt.push(make_pair(1LL, 0LL));

    ll limit_y = pow(n, 1.0/3.0);
    if (limit_y < 1) limit_y = 1;

    while (true) {
        pair<ll, ll> p1 = sbt.top(); sbt.pop();
        ll dh1 = p1.first, dw1 = p1.second;
        
        while (!is_outside(h + dh1, w - dw1, n)) {
            if (w <= dw1) break;
            ret += (i128)h * dw1 + (i128)(dw1 + 1) * (dh1 - 1) / 2;
            ret -= (i128)border * dw1;
            h += dh1;
            w -= dw1;
        }
        
        if (w <= limit_y) break;

        // SB
        ll dh2 = dh1, dw2 = dw1;
        while (!sbt.empty()) {
            pair<ll, ll> top = sbt.top();
            if (is_outside(h + top.first, w - top.second, n)) break;
            sbt.pop();
            dh2 = top.first; dw2 = top.second;
        }
        if (sbt.empty()) break;

        dh1 = sbt.top().first; dw1 = sbt.top().second;
        while (true) {
            ll mh = dh1 + dh2, mw = dw1 + dw2;
            if (!is_outside(h + mh, w - mw, n)) {
                sbt.push(make_pair(mh, mw));
                dh1 = mh; dw1 = mw;
            } else {
                if (slope_steeper(h + mh, w - mw, dh1, dw1)) break;
                dh2 = mh; dw2 = mw;
            }
        }
    }

    for (ll i = 1; i <= w; ++i) {
        ll h_max = (n - i) / (2 * i + 1);
        if (h_max > border) {
            ret += (h_max - border);
        }
    }

    ll ans = (long long)((ret * 2 + border) % MOD);
    cout << (long long)ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
		
    int t;
    if (!(cin >> t)) return 0;
    while (t--) {
        solve();
    }
    return 0;
}
0