记录编号	594979	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 简单的多重背包	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	1.340 s
提交时间	2024-10-06 20:14:05	内存使用	46.48 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100010
#define mod 23333333 
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll n,m;
int dp[5][MAXN],s[5][MAXN],f[1010][MAXN];
ll ef(){
	ll l=1,r=n;
	while(l<r){
		ll mid=(l+r+1)/2;
		if(mid*mid<=n)l=mid;
		else r=mid-1; 
	}
	return l;
}
int main(){
	freopen("get_bag.in","r",stdin);
	freopen("get_bag.out","w",stdout);
	n=read();
	m=ef();
//	m=n;
//	cout<<m<<endl;
//	for(int i=1;i<=n;i++)s[0][i]=1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=i;j++)dp[i&1][j*i]=1;
		for(int j=1;j<=n;j++){
			dp[i&1][j]=(dp[i&1][j]+s[(i-1)&1][j]-s[(i-1)&1][max(0,j-i*(i+1))])%mod;
			dp[(i-1)&1][j]=0;
			s[i&1][j]=(dp[i&1][j]+s[i&1][max(0,j-i-1)])%mod;
//			cout<<dp[i&1][j]<<" ";
		}
//		cout<<endl;
	}
//	cout<<dp[m&1][n]<<endl;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		f[0][i]=dp[m&1][i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
//			f[i][j]=(f[i-1][max((ll)0,(ll)j-m-1)]+f[i][max((ll)0,(ll)j-i)])%mod;
			if(j-m-1>=0)f[i][j]=(f[i][j]+f[i-1][j-m-1])%mod;
			if(j-i>=0)f[i][j]=(f[i][j]+f[i][j-i])%mod;
//			cout<<f[i][j]<<" ";
		}
//		cout<<endl;
	}
//	cout<<f[m-1][n];
	ll ans=0;
	for(int i=0;i<=m;i++)ans=(ans+f[i][n])%mod;
	cout<<ans<<endl;
	return 0;
}