记录编号	617022	评测结果	AAAAAAAAAA
题目名称	3161.HS的自然数拆分	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	4.741 s
提交时间	2026-07-02 19:48:26	内存使用	13.19 MiB

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 300010;
const int Len = 100000;
const long long Mod = 998244353;

int n;
int sqrtn;

int dp1[2][Len + 10];
long long dp1sum[N];

int dp2[Len + 10];
int sum[Len + 10];
long long dp2sum[N];

long long res[N];

template <typename T>
inline T my_pow (T a, T n) {
	T res = 1;
	while (n) {
		if (n & 1) {
			res = res * a % Mod;
		}
		a = a * a % Mod;
		n >>= 1;
	}
	return res % Mod;
}

namespace NTT {
	/*
	require:
		constant : N, Mod
		funcction : my_pow
		head file : algorithm
	*/
	
	const long long rt = 3;
	const long long rti = 332748118;
	long long cc = 0;
	long long limit = 1;
	long long change[N];
	
	void init_limit (const int & n, const int & m) {
		while (limit <= n + m) {
			limit <<= 1;
			cc++;
		}
	}
	
	void init_change () {
		for (int i = 0; i < limit; i++) {
			change[i] = (change[i >> 1] >> 1) | ((i & 1) << (cc - 1));
		}
	}
	
	void init_all (const int & n, const int & m) {
		init_limit (n, m);
		init_change ();
	}
	
	void ntt (long long nums[N], int flag) {
		for (int i = 0; i < limit; i++) {
			if (i < change[i]) {
				std::swap (nums[i], nums[change[i]]);
			}
		}
		
		for (long long mid = 1; mid < limit; mid <<= 1) {
			long long W = my_pow (((flag == 1) ? rt : rti), (Mod - 1) / (mid << 1));
			
			for (long long r = mid << 1, j = 0; j < limit; j += r) {
				long long w = 1;
				
				for (long long l = 0; l < mid; l++, w = w * W % Mod) {
					long long x = nums[j + l];
					long long y = w * nums[j + mid + l] % Mod;
	
					nums[j + l] = (x + y) % Mod;
					nums[j + mid + l] = (x - y + Mod) % Mod;
				}
			}
		}
	}
}

namespace PolynomialMultiplication {
	/*
	require:
		constant : N, Mod
		function : my_pow
		namespace : NTT
	*/
	
	void solve (long long one[N], int n, long long two[N], int m, long long res[N]) {
		NTT::init_all (n, m);
		NTT::ntt (one, 1);
		NTT::ntt (two, 1);
		
		for (int i = 0; i < NTT::limit; i++) {
			res[i] = one[i];
			res[i] *= two[i];
			res[i] %= Mod;
		}
		NTT::ntt (res, -1);
	
		long long inv = my_pow (NTT::limit, Mod - 2);
	
		for (int i = 0; i < n + m + 1; i++) {
			res[i] = res[i] * inv % Mod;
		}
	}
}

int main () {
	
	freopen ("zrscf.in", "r", stdin);
	freopen ("zrscf.out", "w", stdout);
	
	cin >> n;
	sqrtn = sqrt (Len);
	
	// > sqrtn
	dp1[0][0] = 1;
	dp1sum[0] = 1;
	int now = 0;
	for (long long i = 1; i * (sqrtn + 1) <= Len; i++) {
		now ^= 1;
		memset (dp1[now], 0, sizeof (dp1[now]));
		for (int j = i * (sqrtn + 1); j <= Len; j++) {
			dp1[now][j] = (dp1[now ^ 1][j - sqrtn - 1] + dp1[now][j - i]) % Mod;
			dp1sum[j] = (dp1sum[j] + dp1[now][j]) % Mod;
		}
	}
	
	// <= sqrtn
	dp2[0] = 1;
	sum[0] = 1;
	for (int i = 1; i <= sqrtn; i++) {
		for (int j = 0; j <= Len; j++) {
			sum[j] = dp2[j];
			if (j >= i) {
				sum[j] = (sum[j - i] + dp2[j]) % Mod;
			}
		}
		
		for (int j = i; j <= Len; j++) {
			dp2[j] = sum[j];
		}
		memset (sum, 0, sizeof (sum));
	}
	for (int i = 0; i <= Len; i++) {
		dp2sum[i] = dp2[i];
	}
	
	// all
	
	PolynomialMultiplication::solve (dp1sum, Len, dp2sum, Len, res);
	
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;
		cout << res[num] - 1 << endl;
	}
	
	return 0;
}