考虑根号分治：
-
\(i\le \sqrt n\)：做多重背包，可以先做完全背包，再 \(f_j-=f_{j-i(i+1)}\) 减掉不合法的。
-
\(i > \sqrt n\)：每种物品可以看作有无限个，做完全背包，但是直接做还是 \(\mathrm{O(n^2)}\) 的。
类似 \(ARC107D\)，考虑记 \(dp(i,j)\) 为选了 \(i\) 个物品，总体积为 \(j\) 的方案数，有两种决策：
-
添加一个体积为 \(\sqrt n + 1\) 的物品, 即 \(dp(i+1,j+\sqrt n + 1) += dp(i,j)\);
-
给已选的 \(i\ge 1\) 个物品体积均加 \(1\) , 即 \(dp(i,j+i)+=dp(i,j)\) 。
可以证明这种方式可以构造出所有合法方案。
-
总时间复杂度 \(\mathrm{O(n\sqrt n)}\) 。
\(\texttt{Code:}\)
#include <bits/stdc++.h>
#define pb push_back
#define _pr pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define ll long long
using namespace std;
namespace _MoFa {
const int cmd = 23333333;
int _add(int a, int b) {a += b; return a < cmd ? a : a - cmd;}
int _sub(int a, int b) {a -= b; return a < 0 ? a + cmd : a;};
int _mul(int a, int b) {return 1ll * a * b % cmd;}
int fpow(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = _mul(a, a))
if (b & 1) res = _mul(res, a);
return res;
}
}using namespace _MoFa;
inline int read() {
int x = 0, f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return f ? -x : x;
}
const int maxn = 1e5 + 5;
int n, f[maxn], g[320][maxn];
int main() {
n = read();
int B = sqrt(n);
f[0] = 1;
for (int i = 1; i <= B; i++) {
for (int j = i; j <= n; j++) f[j] = _add(f[j], f[j - i]);
for (int j = n; j >= i * (i + 1); j--)
f[j] = _sub(f[j], f[j - i * (i + 1)]);
}
g[0][0] = 1;
for (int i = 0; i <= B; i++)
for (int j = 0; j <= n; j++) {
if (j + B + 1 <= n) g[i + 1][j + B + 1] = _add(g[i + 1][j + B + 1], g[i][j]);
if (i && j + i <= n) g[i][j + i] = _add(g[i][j + i], g[i][j]);
}
int ans = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= B; j++)
ans = _add(ans, _mul(f[i], g[j][n - i]));
printf("%d", ans);
return 0;
}