LOJ #6089. 小 Y 的背包计数问题 题解

Description

小 Y 有一个大小为 $n$ 的背包，并且小 Y 有 $n$ 种物品。

对于第 $i$ 种物品，共有 $i$ 个可以使用，并且对于每一个 $i$ 物品，体积均为 $i$。

求小 Y 把该背包装满的方案数为多少，答案对于 $23333333$ 取模。

定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。

$1\leq n\leq 10^5$。

Solution

首先有个暴力的做法是设 $f_{i,j}$ 表示前 $i$ 种物品，体积为 $j$ 的方案数，那么可以得到转移：

$$f_{i,j}=\sum_{k=0}^{i}{f_{i-1,j-ik}}$$

注意到转移到 $j$ 的一定是与 $j$ 模 $i$ 同余的数的连续段，用前缀和维护即可做到 $O(n^2)$。

容易发现上面那个做法慢在没有利用到某些物品出现次数不多的性质。

可以考虑对于 $\leq\sqrt n$ 的数可以暴力做。而 $>\sqrt n$ 的数不可能达到次数限制并且这部分最多选 $\sqrt n$ 个，要单独处理。

如果直接 dp 显然无法用到选的个数不多的性质。

注意到如果把第 $i$ 种物品看成长度为 $i$ 的竖条，那么刚才那个做法是横着进行 dp。又因为列数是不多的，所以可以考虑竖着 dp。这样相当于就是对不超过 $\sqrt n$ 个物品进行多重背包。

具体的，可以从高向低枚举，每次有两种操作：加入一个高度为 $\sqrt n+1$ 的长条，和将当前已经加进去的长条整体长度加 $1$。显然这两种操作可以构造出所有合法的序列。

设 $f_{i,j}$ 表示当前有 $i$ 个长条，长度之和为 $j$ 的方案数，转移如下：$f_{i,j+i}\leftarrow f_{i,j},f_{i+1,j+\sqrt n+1}\leftarrow f_{i,j}$。

最后求答案就将两个部分拼起来即可。

时间复杂度：$O(n\sqrt n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5, kMaxB = 325, kMod = 23333333;

int n, b;
int f[kMaxN], g[kMaxN];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void solve1() {
  static int sum[kMaxN];
  f[0] = 1;
  for (int i = 1; i <= b; ++i) {
    for (int j = 0; j <= n; ++j) {
      sum[j] = add(f[j], (j < i) ? 0 : sum[j - i]);
      int p = j - i * (i + 1);
      f[j] = sub(sum[j], (p < 0) ? 0 : sum[p]);
    }
  }
}

void solve2() {
  static int f[kMaxB][kMaxN];
  f[0][0] = 1;
  for (int i = 0; i <= n / b; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i && j + i <= n) inc(f[i][j + i], f[i][j]);
      if (j + b + 1 <= n) inc(f[i + 1][j + b + 1], f[i][j]);
      inc(g[j], f[i][j]);
    }
  }
}

void dickdreamer() {
  std::cin >> n;
  b = sqrt(n);
  solve1(), solve2();
  int ans = 0;
  for (int i = 0; i <= n; ++i) inc(ans, 1ll * f[i] * g[n - i] % kMod);
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}