https://www.zybuluo.com/ysner/note/1285358
题面
小(Y)有一个大小为(n)的背包，并且小(Y)有(n)种物品。
对于第(i)种物品，共有(i)个可以使用，并且对于每一个(i)物品，体积均为(i)。
求小(Y)把该背包装满的方案数为多少，答案对于(23333333)取模。
定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。
- (nleq10^5)
解析
这个背包问题让我耳目一新啊。
(idea)棒棒的。
注意到题目中物品(i)（(igeqsqrt n))的个数限制实际上是不存在的。
所以可以把这个问题分为两个子问题：多重背包问题和完全背包问题。
设(f[i][v])表示前(i)个物品，总体积为(v)时的方案数。
对于(ileqsqrt n)：（多重背包问题）
很显然有$$f[i][v]=sum_{j=1}^if[i-1][v-j*i]$$
可以前缀和优化做到(O(nsqrt n))。
对于(igeqsqrt n)：（完全背包问题）
又注意到一个物品最多取(sqrt n)个。
同样设个(g[i][v])表示方案数。
可以认为我们要(DP)出一个和为(n)，最小数至少(sqrt n+1)的不下降序列
（序列中的数是物品体积）。
转移有两种：
- 在序列开头加入一个数(sqrt n+1)
- 把序列中所有数(+1)
则$$g[i][v]=g[i-1][v-sqrt n-1]+g[i][v-i]$$
这个复杂度(O(n))？
最后讨论一下给前一个问题分配多少体积，后一个问题分配多少体积，统计答案即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2005,inf=2e9,mod=23333333;
int n,f[N],g[350][N],s[N],ans=-inf,m;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int main()
{
n=gi();m=sqrt(n);
f[0]=1;
fp(i,1,m)
{
fp(j,0,i) s[j]=f[j];
fp(j,i,n) s[j]=(f[j]+s[j-i])%mod;//前缀和
fp(j,0,n)
{
f[j]=s[j];
if(j-i*(i+1)>=0) f[j]=(f[j]-s[j-i*(i+1)]+mod)%mod;//去掉不合法状态
}
}
g[0][0]=1;ans=f[n];
fp(i,1,m)
for(re int j=i*(m+1);j<=n;j++)
{
g[i][j]=(g[i-1][j-m-1]+g[i][j-i])%mod;
(ans+=1ll*g[i][j]*f[n-j]%mod)%=mod;
}
printf("%d
",ans);
return 0;
}