数列 | dp/背包 - ThuNov28 2024

maka_baka · 2024-11-28 08:43:19 · 题解

给定整数 n，m，r，和价值函数 v:[0,m]\rightarrow[1,P)。当然限定这个区间是整数的子集。设 \mathrm{popcount}(x) 表示 x 的二进制位中 1 的个数，我们喜欢这样的序列 \{a\}：

|\{a\}|=n,\qquad\mathrm{popcount}(\sum_{i=1}^n2^{a_i})\le r.

对于我们喜欢的所有序列，求下面的和：

A=\sum_{\{a\}}\prod_{i=1}^nv(a_i)

输出 A\bmod P 的值。

直接枚举数列里每个数的取值可以有部分分，但还可以做得更好。

数列约束条件和排列方式无关，我们考虑根据每个数出现次数来给序列分类。我用 \langle b_0,b_1,b_2,\cdots,b_m\rangle 表示 0 出现了 b_0 次，1 出现了 b_1 次，……，m 出现了 b_m 次的序列。比如说，[1,2,0,1,2] 和 [0, 1, 2, 2, 1] 都是 \langle 1,2,2\rangle 这一类的。样例里，我们喜欢的数列就是 \langle 2,3\rangle。

进一步地，这道题可以看成一个背包：物品编号 [0,m]，第一维容量是 n（要刚好用完），第二位是 \mathrm{popcount}，可以有剩余。我们要计算选法价值之积。

这是多重背包，每个物品（可能）可以选 n 个，可能不选。类比板子状态：(i,j) 是（物品种类，容量），转移方法：

我们先调整限制（物品种类，容量），计算每个子问题答案，再从所有子问题中选取和原问题的方案。

TIP 这个思想很有用。这样子我们在转移时不用考虑原问题的限制。由于第二个体积计算方法很特殊，我们可以用其它的约束代替它，最后在考虑怎样的约束之并可以等价于 \mathrm{popcount} 的约束。

模拟二进加法，我们发现当 \{a\} 比较小的数（[0,i]）确定次数后，S=\sum2^a 的低位（[0,i] 位）也确定了，假设我们把进位只进行 [0,i-1]，那 i 位会累积一些数，当我们决定不选这些了，就把这些数要进位的堆到下一位，i'=i+1，第 i 位收到 [0,i'-1] 里面去，如此往复。

统计答案时，枚举 “[0,n-1] 位 1 的个数” 和 n 位 “堆叠 1 的个数” 二进制表示下 1 的个数，它们之和不大于 r，第二个重量就满足了。

设 (i,j,k,x) 表示只在 [0,i] 内选物品，一共选了 j 个，二进制数第 i 位堆了 k 个 1，[0,i-1] 存了 x 个 1，这样子的序列的答案。转移时也是选和不选。选一个 i：

为了方便，用 / 表示下取整除法，\bmod 的优先级在乘法和乘方之间。不选，开始下一轮选数：

可是这个转移是错的。因为向原序列插入一个新的数时，表面上有 (j+1) 个位置，但因为这个序列里本身可能就有 i，会算重。比如这两个加入 2 后的序列就重了：

[1 2 0] -> [1 2 (2) 0] [1 (2) 2 0]

有 2 个补救方法：

• 添加一维状态 t\ge k，表示当前的数选了 t 个，选数时转移到 t'=t+1，不选数时转移到 t'=0。
• 修改转移方式，直接枚举选几个数，转移到下一轮选数中。

我选择后者。对于当前状态，枚举选谁，和实现方法（填表/刷表）有关。这道题刷表法好写，那就是假设 [0,i] 都选完了，枚举 (i+1) 选 y 个，转移方向：

填表是枚举未求解的状态；刷表 是枚举已求解的状态，更新可能被用来转移的未解状态。

从表达式能看出，我们从后者推出它依赖哪些状态很麻烦，而从已知状态更新未知却很容易。实现时，可能有多个已知状态对应未知状态，把每次更新的值求和即可。

明确方向后，表达式就是水到渠成的事情了。因为原序列不含 i+1，所以不同的插入方法，就是在新的 (j+y) 个数中，选 y 个变成 i+1，其它的按原来顺序填入 j 个数，共有 \binom{j+y}y 种。

边界如下，对于 i=0 的其它状态属于不合法状态（比如 j\ne k），均赋成 0：

由于不合法的状态，都只能由 f 为 0 的状态转移过去，所以不用担心出错。实现时，枚举 i\in[0,m)，0\le x,y\le j\le n 即可。用时 O(mn^4)。

组合数 \binom ce 定义域是 c\ge0，0\le e\le c，不要写错了。

AC Code

#include <iostream>
using ll = long long;
const ll P = 998244353;
const int N = 33, M = 105;

int n, m, r;
ll f[M][N][N][N],
   v[M][N], w[N][N], ans;

int pop(int x) {
  int u = 0;
  while (x) u++, x ^= x & -x;
  return u;
}

int main() {
  std::cin >> n >> m >> r;
  for (int i=0; i<=m; i++) {
    v[i][0]=1, std::cin >> v[i][1];
    for (int j=2; j<=n; j++)
      v[i][j] = v[i][1] * v[i][j-1] % P;
  }

  for (int i=0; i<=n; i++)
    w[i][0] = w[i][i] = 1;
  for (int i=2; i<=n; i++)
    for (int j=1; j<=i-1; j++)
      w[i][j] = (w[i-1][j-1]
          + w[i-1][j]) % P;

  for (int j=0; j<=n; j++)
    f[0][j][j][0] = v[0][j];

  for (int i=0; i<m; i++)
    for (int j=0; j<=n; j++)
    for (int k=0; k<=j; k++)
    for (int x=0; x<=j; x++)
    for (int y=0; j+y<=n; y++) {
      ll &f1 = f[i+1][j+y][y+k/2][x+k%2];
      f1 = (f[i][j][k][x] * v[i+1][y] % P
        * w[j+y][y] % P + f1) % P ;
    }

  for (int k=0; k<=n; k++)
    for (int x=0; x<=r; x++)
    if (pop(k)+x<=r)
      ans = (ans+f[m][n][k][x]) % P;
  std::cout << ans << '\n';
}