結果

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

ソースコード

diff #
raw source code 

// https://atcoder.jp/contests/abc230/submissions/60477016
// 1 "library/Template/template.hpp"
#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--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using uint = unsigned int;
using ll = __int128_t;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return 1;
	}
	return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return 1;
	}
	return 0;
}
template <typename T, typename U>
T ceil(T x, U y) {
	assert(y != 0);
	if (y < 0)
		x = -x, y = -y;
	return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
	assert(y != 0);
	if (y < 0)
		x = -x, y = -y;
	return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T>
int popcnt(T x) {
	return __builtin_popcountll(x);
}
template <typename T>
int topbit(T x) {
	return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T>
int lowbit(T x) {
	return (x == 0 ? -1 : __builtin_ctzll(x));
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
	os << "P(" << p.first << ", " << p.second << ")";
	return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	os << "{";
	for (int i = 0; i < vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
	}
	os << "}";
	return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
	os << "{";
	for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
		os << "(" << itr->first << ", " << itr->second << ")";
		itr++;
		if (itr != map_var.end())
			os << ", ";
		itr--;
	}
	os << "}";
	return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
	os << "{";
	for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
		os << *itr;
		++itr;
		if (itr != set_var.end())
			os << ", ";
		itr--;
	}
	os << "}";
	return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
	for (; a[i] != ',' && a[i] != '\0'; i++)
		cerr << a[i];
	cerr << ":" << b << " ";
	_show(i + 1, a, c...);
}

/**
 * @brief Fast IO
 */
// // 3 "sol.cpp"

template <unsigned mod = 1000000007>
struct fp {
	unsigned v;
	static constexpr int get_mod() {
		return mod;
	}
	constexpr unsigned inv() const {
		assert(v != 0);
		int x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
		while (y > 0) {
			t = x / y;
			x -= t * y, p -= t * q;
			tmp = x, x = y, y = tmp;
			tmp = p, p = q, q = tmp;
		}
		if (p < 0)
			p += mod;
		return p;
	}
	constexpr fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
	fp operator-() const {
		return fp() - *this;
	}
	fp pow(ull t) {
		fp res = 1, b = *this;
		while (t) {
			if (t & 1)
				res *= b;
			b *= b;
			t >>= 1;
		}
		return res;
	}
	fp &operator+=(const fp &x) {
		if ((v += x.v) >= mod)
			v -= mod;
		return *this;
	}
	fp &operator-=(const fp &x) {
		if ((v += mod - x.v) >= mod)
			v -= mod;
		return *this;
	}
	fp &operator*=(const fp &x) {
		v = ull(v) * x.v % mod;
		return *this;
	}
	fp &operator/=(const fp &x) {
		v = ull(v) * x.inv() % mod;
		return *this;
	}
	fp operator+(const fp &x) const {
		return fp(*this) += x;
	}
	fp operator-(const fp &x) const {
		return fp(*this) -= x;
	}
	fp operator*(const fp &x) const {
		return fp(*this) *= x;
	}
	fp operator/(const fp &x) const {
		return fp(*this) /= x;
	}
	bool operator==(const fp &x) const {
		return v == x.v;
	}
	bool operator!=(const fp &x) const {
		return v != x.v;
	}
	friend istream &operator>>(istream &is, fp &x) {
		return is >> x.v;
	}
	friend ostream &operator<<(ostream &os, const fp &x) {
		return os << x.v;
	}
};

template <typename T>
T Inv(ll n) {
	static int md;
	static vector<T> buf({0, 1});
	if (md != T::get_mod()) {
		md = T::get_mod();
		buf = vector<T>({0, 1});
	}
	assert(n > 0);
	n %= md;
	while (SZ(buf) <= n) {
		int k = SZ(buf), q = (md + k - 1) / k;
		buf.push_back(buf[k * q - md] * q);
	}
	return buf[n];
}

template <typename T>
T Fact(ll n, bool inv = 0) {
	static int md;
	static vector<T> buf({1, 1}), ibuf({1, 1});
	if (md != T::get_mod()) {
		md = T::get_mod();
		buf = ibuf = vector<T>({1, 1});
	}
	assert(n >= 0 and n < md);
	while (SZ(buf) <= n) {
		buf.push_back(buf.back() * SZ(buf));
		ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
	}
	return inv ? ibuf[n] : buf[n];
}

template <typename T>
T nPr(int n, int r, bool inv = 0) {
	if (n < 0 || n < r || r < 0)
		return 0;
	return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T>
T nCr(int n, int r, bool inv = 0) {
	if (n < 0 || n < r || r < 0)
		return 0;
	return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
// sum = n, r tuples
template <typename T>
T nHr(int n, int r, bool inv = 0) {
	return nCr<T>(n + r - 1, r - 1, inv);
}
// sum = n, a nonzero tuples and b tuples
template <typename T>
T choose(int n, int a, int b) {
	if (n == 0)
		return !a;
	return nCr<T>(n + b - 1, a + b - 1);
}

namespace Random {
mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long;
u64 get() {
	return randgen();
}
template <typename T>
T get(T L) { // [0,L]

	return get() % (L + 1);
}
template <typename T>
T get(T L, T R) { // [L,R]

	return get(R - L) + L;
}
double uniform() {
	return double(get(1000000000)) / 1000000000;
}
string str(int n) {
	string ret;
	rep(i, 0, n) ret += get('a', 'z');
	return ret;
}
template <typename Iter>
void shuffle(Iter first, Iter last) {
	if (first == last)
		return;
	int len = 1;
	for (auto it = first + 1; it != last; it++) {
		len++;
		int j = get(0, len - 1);
		if (j != len - 1)
			iter_swap(it, first + j);
	}
}
template <typename T>
vector<T> select(int n, T L, T R) { // [L,R]

	if (n * 2 >= R - L + 1) {
		vector<T> ret(R - L + 1);
		iota(ALL(ret), L);
		shuffle(ALL(ret));
		ret.resize(n);
		return ret;
	} else {
		unordered_set<T> used;
		vector<T> ret;
		while (SZ(used) < n) {
			T x = get(L, R);
			if (!used.count(x)) {
				used.insert(x);
				ret.push_back(x);
			}
		}
		return ret;
	}
}

void relabel(int n, vector<pair<int, int>> &es) {
	shuffle(ALL(es));
	vector<int> ord(n);
	iota(ALL(ord), 0);
	shuffle(ALL(ord));
	for (auto &[u, v] : es)
		u = ord[u], v = ord[v];
}
template <bool directed, bool simple>
vector<pair<int, int>> genGraph(int n) {
	vector<pair<int, int>> cand, es;
	rep(u, 0, n) rep(v, 0, n) {
		if (simple and u == v)
			continue;
		if (!directed and u > v)
			continue;
		cand.push_back({u, v});
	}
	int m = get(SZ(cand));
	vector<int> ord;
	if (simple)
		ord = select(m, 0, SZ(cand) - 1);
	else {
		rep(_, 0, m) ord.push_back(get(SZ(cand) - 1));
	}
	for (auto &i : ord)
		es.push_back(cand[i]);
	relabel(n, es);
	return es;
}
vector<pair<int, int>> genTree(int n) {
	vector<pair<int, int>> es;
	rep(i, 1, n) es.push_back({get(i - 1), i});
	relabel(n, es);
	return es;
}
}; // namespace Random
using mint = atcoder::modint998244353;

mint solve(ll n) {

	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 x * y > n;
	};
	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) / 2;
			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 = -n;
		ans += solve(n) - 2 * solve(n / 2) + solve(n / 4);
		cout << ans.val() << endl;
	}
}
0