[51nod1597] 有限背包计数问题

题目大意

你有一个大小为n的背包，你有n种物品，第i种物品的大小为i，且有i个，求装满这个背包的方案数有多少
两种方案不同当且仅当存在至少一个数i满足第i种物品使用的数量不同

n≤100000，答案模23333333，时限2.333s

分析

这道题一看是一道多重背包，但是范围有点大啊。。。
可以尝试利用一下题目的条件，对于 i≤n√ ，就做一次多重背包。合并一种物品时，通过前缀和可以优化到O(n)。
对于 i>n√ ，可以当成完全背包来做！
但是直接上完全背包又很慢。。。
但是可以注意到另一点：这些物品使用个数也不超过 n√ ，那么一个思路出来了：设g[i][j]表示用i个物品，体积为j的方案数。
转移： g[i][j]=g[i][j−i]+g[i−1][j−n√−1] 。第一个表示把当前i个物品的体积都加1，第二个表示加入一个体积为 n√+1 的物品。由于加入物品的体积是不上升的，所以是正确的。
时间复杂度 O(nn√)

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=100005,mo=23333333;

typedef long long LL;

int n,g[2][N],p,q,m,f[2][N],s,t,ans;

int main()
{
scanf("%d",&n);
for (m=n;m>n/m;m--);
    p=0; q=1; f[0][0]=1;
for (int i=1;i<=m;i++,p^=1,q^=1)
    {
memset(f[q],0,sizeof(f[q]));
for (int j=0;j<i;j++)
        {
            s=0;
for (int k=0;k*i+j<=n;k++)
            {
                s=(s+f[p][k*i+j])%mo;
                f[q][k*i+j]=s;
if (k>=i) s=(s+mo-f[p][(k-i)*i+j])%mo;
            }
        }
    }
    t=p; ans+=f[t][n];
    g[0][0]=1; p=0; q=1;
for (int i=1;i<=m;i++,p^=1,q^=1)
    {
memset(g[q],0,sizeof(g[q]));
for (int j=m+1;j<=n;j++)
        {
            g[q][j]=g[p][j-m-1];
if (j>=i) g[q][j]=(g[q][j]+g[q][j-i])%mo;
        }
for (int j=0;j<=n;j++) ans=(ans+(LL)f[t][j]*g[q][n-j])%mo;
    }
printf("%d\n",ans);
return 0;
}