记录编号	616812	评测结果	AAAAAAAAAA
题目名称	2297.[HZOI 2015] 简单的多重背包	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	1.054 s
提交时间	2026-06-30 19:54:09	内存使用	7.82 MiB

#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>

using namespace std;

const int N = 114514;
const int SqrtN = 514;
const int Mod = 23333333;

int n;
int sqrtn;

long long dp1[2][N];
long long dp1sum[N];

long long sum[2][N];
long long dp2[N];
long long dp2sum[N];

long long res;

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