luogu.p7961.md

数列 | dp/背包 - ThuNov28 2024

Luogu P7961 给定整数 $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$ 的值。

$1\le r\le n$，$8\le n\le30$，$9\le m\le100$，$1\le v_i\le P-1$，$P=998244353$。

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

数列约束条件和排列方式无关，我们考虑根据每个数出现次数来给序列分类。我用 $\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)$ 是（物品种类，容量），转移方法： $$(i,j)\rightarrow(i+1,j)\text{ or } (i,j+w_i)$$ 我们先调整限制（物品种类，容量），计算每个子问题答案，再从所有子问题中选取和原问题的方案。

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$： $$(i,j,k,x)\rightarrow(i,j+1,k+1,x)$$ 为了方便，用 $/$ 表示下取整除法，$\bmod$ 的优先级在乘法和乘方之间。不选，开始下一轮选数： $$(i,j,k,x)\rightarrow(i+1,j,k/2,x+k\bmod2)$$ 可是这个转移是错的。因为向原序列插入一个新的数时，表面上有 $(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,j,k,x)\rightarrow(i+1,j+y,k/2+y,x+k\bmod2)$$

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

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

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

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

由于不合法的状态，都只能由 $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';
}

请求添加题解

@Acoipp @是青白呀 文章链接

这篇文章详细地说明了做法的动机、流程，总结出了一些 DP 思想，如 “约束转换” “转移方向” “修正状态” “非法状态” 等。

题解区目前没有对这些明确总结的题解，多以阐述流程，展示结论等，对同学们（比如一个月前的我）极不友好，我的文章完善了这部分的逻辑链，代码比较工整（没有太多的细节变化），望采纳。