题意
Sol
不会做啊AAA。。
暴力上肯定是不行的，考虑根号分组
设\(m = \sqrt{n}\)
对于前\(m\)个直接暴力，利用单调队列优化多重背包的思想，按\(\% i\)分组一下。复杂度\(O(n\sqrt{n})\)
对于后\(m\)个，此时每个物品没有个数的限制，换一种dp方法
设\(g[i][j]\)表示用了\(i\)个物品，大小为\(j\)的方案数。
转移的时候有两种方案
把当前所有物品大小\(+1\)，\(g[i][j + i] += g[i][j]\)
新加入一个最小的物品, \(g[i + 1][j + m + 1] += g[i][j]\)
看上去很显然，但自己想不出来qwq
#include#include #include #define pt(x) printf("%d\n", x);using namespace std;const int MAXN = 1e5 + 10, mod = 23333333;int N, M, f[81][MAXN], g[81][MAXN];int add(int x, int y) { return (x + y >= mod) ? (x + y - mod): x + y;}int main() { scanf("%d", &N); M = sqrt(N); /*f[0][0] = 1; int o = 1; for(int i = 1; i <= M; i++) { for(int k = 0; k < i; k++) {//res int s = 0; for(int t = 0; i * t + k <= N; t++) {//num s = add(s, f[i - 1][k + t * i]); f[i][k + t * i] = s; if(t >= i) s = (s - f[i - 1][(t - i) * i + k] + mod) % mod;//over take } } } int ans = f[M][N]; pt(ans) g[0][0] = 1; int p = 0; for(int i = 1; i <= M; i++) {// used i goods for(int j = 0; j <= N; j++) {// length is j if(j >= M + 1) g[i][j] = g[i - 1][j - (M + 1)]; if(j >= i) g[i][j] = add(g[i][j], g[i][j - i]); } for(int j = 0; j <= N; j++) (ans += 1ll * f[M][j] * g[i][N - j] % mod) %= mod; } printf("%d", ans);*/ f[0][0] = 1; int o = 1; for(int i = 1; i <= M; i++, o ^= 1) { memset(f[o], 0, sizeof(f[o])); for(int k = 0; k < i; k++) {//res int s = 0; for(int t = 0; i * t + k <= N; t++) {//num s = add(s, f[o ^ 1][k + t * i]); f[o][k + t * i] = s; if(t >= i) s = (s - f[o ^ 1][(t - i) * i + k] + mod) % mod;//over take } } } int ans = f[o ^ 1][N], tmp = o ^ 1; pt(ans) g[0][0] = 1; o = 1; for(int i = 1; i <= M; i++, o ^= 1) {// used i goods memset(g[o], 0, sizeof(g[o])); for(int j = 0; j <= N; j++) {// length is j if(j >= M + 1) g[o][j] = g[o ^ 1][j - (M + 1)]; if(j >= i) g[o][j] = add(g[o][j], g[o][j - i]); } for(int j = 0; j <= N; j++) (ans += 1ll * f[tmp][j] * g[o][N - j] % mod) %= mod; } printf("%d", ans); return 0;}