记录编号	595094	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 简单的多重背包	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	1.809 s
提交时间	2024-10-08 19:53:44	内存使用	89.28 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const long long mod=23333333;
int n,sq;
long long ans,f[2][100010],g[320][100010],f1[100010],f2[100010];
void work1() 
{
	f[0][0]=1;
	for(int i=1,t=1;i<=sq;i++,t^=1)
	{
	    for(int j=0;j<=n;j++) 
        {
			f[t][j]=f[t^1][j];
			if(j>=i) f[t][j]=(f[t][j]+f[t][j-i])%mod;
			if(j>=i*(i+1)) f[t][j]=(f[t][j]-f[t^1][j-i*(i+1)]+mod)%mod;
		}
    }
	for(int i=0;i<=n;i++)
    {
        f1[i]=f[sq&1][i];
    } 
}
void work2() 
{
	g[0][0]=1;
	for(int i=0;i<=sq;i++)
	{
	    for(int j=0;j<=n;j++) 
        {
			f2[j]=(f2[j]+g[i][j])%mod;
			if(i&&j+i<=n) g[i][j+i]=(g[i][j+i]+g[i][j])%mod;
			if(j+sq+1<=n) g[i+1][j+sq+1]=(g[i+1][j+sq+1]+g[i][j])%mod;
		}
    }	
}
int main()
{
    freopen("get_bag.in","r",stdin);
    freopen("get_bag.out","w",stdout);
	scanf("%d",&n);
    sq=sqrt(n);
	work1();
    work2();
	for(int i=0;i<=n;i++)
    {
        ans=(ans+f1[i]*f2[n-i]%mod)%mod;
    } 
	printf("%lld",ans);
	return 0;
}