https://class.51nod.com/Html/Textbook/ChapterIndex.html#chapterId=335&textbookId=126
https://class.51nod.com/Html/Challenge/Problem.Html#problemId=1597
如有限背包计数问题
发现对于物品 \(i\) 最多填充 \(i*i\)，而对于 \(i>\sqrt n\) 可以视为完全背包，所以我们分为两类。
对于小的那一类，可以用临时数组维护对应余数的和（像多重背包一样），然后超出范围的再减去。
大的那一类，考虑每次添加一个新的数或者让所有数+1（这样就能涵盖所有的情况，所有数+1相当于偏移，你想让它等于多少，就在最后一个数加入前特定时间加入即可）。
复杂度 \(O(n\sqrt n)\)。
#include<iostream>
#include<cmath>
#include<cstring>
#define add(a,b) (a+=b)>=mod&&(a-=mod)
#define sub(a,b) (a-=b)<0&&(a+=mod)
using namespace std;
const int N=100010,mod=23333333,Q=320;
int n,q,tmp[Q],f[2][N],g[2][N];
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n;
q=sqrt(n)+1;
f[0][0]=1;
for(int i=1;i<q;++i){
int I=i&1,L=!I;
memset(tmp,0,i*4);
int mo=-1;
for(int j=0;j<=n;++j){
++mo;
if(mo==i)mo=0;
add(tmp[mo],f[L][j]);
f[I][j]=tmp[mo];
if(j>=i*i)sub(tmp[mo],f[L][j-i*i]);//can't reach
}
}
int qq=(q-1)&1;
// for(int i=1;i<q;++i,puts(""))
// for(int j=0;j<=n;++j)
// cout<<f[i][j]<<' ';
g[0][0]=1;
int ans=f[qq][n],nq=n/q;
for(int i=1;i<=nq;++i){int I=i&1,L=!I;
g[I][0]=0;
for(int j=q;j<=n;++j){
g[I][j]=g[L][j-q];
add(g[I][j],g[I][j-i]);
add(ans,1ll*g[I][j]*f[qq][n-j]%mod);
}}
cout<<ans;
return 0;
}