记录编号	616534	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 简单的多重背包	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	0.859 s
提交时间	2026-06-26 20:06:54	内存使用	4.58 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int mod = 23333333;
int n, m, f[2][N], F[N], g[2][N], G[N], ans;
inline void Add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	return;
}
inline void Sub(int &x, int y) {
	x -= y;
	if (x < 0) x += mod;
	return;
}
int main() {
	cin >> n;
	m = ceil(sqrt(n));
	f[0][0] = 1;
	for (int i = 1; i <= m; i++) {
		int o = (i & 1);
		for (int j = 0; j <= n; j++) {
			f[o][j] = f[o ^ 1][j];
			if (j >= i) Add(f[o][j], f[o][j - i]);
		}
		for (int j = n; j >= 0; j--) {
			if (j >= i * (i + 1)) Sub(f[o][j], f[o][j - i * (i + 1)]);
		}
		for (int j = 0; j <= n; j++) {
			f[o ^ 1][j] = 0;
		}
	}
	for (int j = 0; j <= n; j++) {
		F[j] = f[m & 1][j];
	}
	g[0][0] = 1;
	for (int i = 1; i <= m; i++) {
		int o = (i & 1);
		for (int j = 0; j <= n; j++) {
			if (j >= i) Add(g[o][j], g[o][j - i]);
			if (j >= m + 1) Add(g[o][j], g[o ^ 1][j - m - 1]);
		}
		for (int j = 0; j <= n; j++) {
			Add(G[j], g[o ^ 1][j]);
			g[o ^ 1][j] = 0;
		}
	}
	for (int i = 0; i <= n; i++) {
		Add(ans, 1ll * F[i] * G[n - i] % mod);
	}
	cout << ans << '\n';
	return 0;
}