結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー 遭難者
提出日時 2025-12-23 01:25:54
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,551 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,923 ms
コンパイル使用メモリ 336,332 KB
実行使用メモリ 20,128 KB
最終ジャッジ日時 2025-12-23 01:26:09
合計ジャッジ時間 14,479 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// https://atcoder.jp/contests/abc230/submissions/60477016
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)

using ll = int64_t;
using i128 = __int128_t;

using mint = atcoder::modint998244353;

mint solve(ll n) {
	const mint two_inv = mint(2).inv();
	ll SQ = sqrtl(n), CB = cbrtl(n);
	ll x = n / SQ, y = SQ + 1;
	mint ret = 0;
	using P = pair<ll, ll>;
	stack<P> sbt({{1, 0}, {1, 1}});
	auto inside = [&](ll x, ll y) {
		return y != 0 && x > n / y;
	};
	auto cut = [&](ll x, P p) {
		return i128(n) * p.first <= i128(x) * x * p.second;
	};

	for (;;) {
		auto [dx1, dy1] = sbt.top();
		sbt.pop();
		while (inside(x + dx1, y - dy1)) {
			ret += x * (mint)dy1 + (dy1 + 1) * (mint)(dx1 - 1) * two_inv;
			x += dx1, y -= dy1;
		}
		if (y <= CB) break;
		ll dx2 = dx1, dy2 = dy1;
		while (!sbt.empty()) {
			tie(dx1, dy1) = sbt.top();
			if (inside(x + dx1, y - dy1)) break;
			sbt.pop();
			dx2 = dx1, dy2 = dy1;
		}
		if (sbt.empty()) break;

		for (;;) {
			ll mx = dx1 + dx2, my = dy1 + dy2;
			if (inside(x + mx, y - my)) {
				sbt.push({dx1 = mx, dy1 = my});
			} else {
				if (cut(x + mx, P{dx1, dy1})) break;
				dx2 = mx, dy2 = my;
			}
		}
	}
	rep(i, 1, y) ret += n / i;
	ret = ret * 2 - SQ * SQ;
	return ret;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		long n;
		cin >> n;
		n = 2 * n + 1;
		mint ans = solve(n) - 2 * solve(n / 2) + solve(n / 4) - n;
		cout << ans.val() << endl;
	}
}
0