litble 刚刚发了一篇介绍五边形数定理做整数划分，能做到 $O(n \sqrt n)$预处理，$O(1)$询问的文章，可以戳这里：https://www.mina.moe/archives/10981

$$f[i][j] = f[i – 1][j – \sqrt n] + f[i][j – i]$$

#include <bits/stdc++.h>

#define NS (200005)
#define MOD (999999599)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, k, f[NS], g[2][NS], h[NS];

int main(int argc, char const* argv[])
{
IN(n), k = sqrt(n), f[0] = 1;
for (int i = 1; i < k; i += 1)
for (int j = i; j <= n; j += 1)
f[j] = (f[j] + f[j - i]) % MOD;
g[0][0] = h[0] = 1; bool cur = 0;
for (int i = 1; i <= n / k; i += 1)
{
cur ^= 1, memset(g[cur], 0, sizeof(int) * (n + 1));
for (int j = 0; j <= n; j += 1)
{
if (j >= k) g[cur][j] = (g[cur][j] + g[cur ^ 1][j - k]) % MOD;
if (j >= i) g[cur][j] = (g[cur][j] + g[cur][j - i]) % MOD;
}
for (int j = 0; j <= n; j += 1) h[j] = (h[j] + g[cur][j]) % MOD;
}
int tot = 0;
for (int i = 0; i <= n; i += 1)
tot = (tot + (1ll * f[i] * h[n - i] % MOD)) % MOD;
printf("%d\n", tot);
return 0;
}


#### Remmina

No puzzle that couldn't be solved.