打卡第三天 - P2946 - 2026 - 6 - 16

2026/6/17 0:55:07

这是也是一道01背包的题目，只不过动规数组的定义有点出乎我的意料，因为最终的结果需要Mod F,所以我们定义动规数组$f[i][j]$是考虑前i个数的情况下组合出来的能力值对F取模的结果为j的方案数。
这样，我们就可以套01背包的模板了，就是递推部分需要改一改
当选到第i个的时候，我们有两种情况

不选这个牛，我们的方案就来自于$f[i-1][j]$，原样递推过来
选这个牛，我们的方案数就来自于$f[i-1][(j - (r_i \bmod F ) + F) \bmod F]$，为什么呢，因为我们需要找一个方案，原本的能力值加上当前的$r_i$然后对F取余得j，设原本的能力值为$x$，则得$$(x + r_i) \bmod F = j$$根据$$a\bmod m=b⟺a=km+b (k∈Z,0≤b<m)$$可得$$x+r_i = kF + j$$整理得$$x=kF+(j-r_i)$$所以$$x \equiv (j-r_i) \pmod{F}$$意味着$x$与$j-r_i$的差是$F$的倍数，因此$$x \bmod F = (j - r_i) \bmod F$$因为$x$的定义域为$0\le x <F$，则$$x=(j-r_i)\bmod F$$因为不确定$j$和$r_i$的大小关系，防止中间得到负数，我们加一个F，即$$x=(j-r_i+F)\bmod F$$但是，$r_i$的定义域为$0\le r_i \le 10^5$，$j$的定义域却为$0\le j < F$，就有可能出现$r_i$比$j$大很多，导致我们加一个$F$可能还是负数，所以我们根据 $$(a+b) \bmod c = (a + (b \bmod c)) \bmod c$$可得$$x=(j-r_i+F)\bmod F \iff x=(j-(r_i \bmod F) + F) \bmod F $$故我们终于推导出了结果，但是解题还没有结束
因为这两种情况都合法，所以我们在计算方案总数的时候要把两个都算上而不是用max
所以完整的递推公式为$$f[i][j]=f[i-1][j] + f[i-1][(j - (r_i \bmod F) + F) \bmod F] \bmod 10^8$$
记得对1e8求余，不然很容易爆int
然后，我们就可以轻松愉快的写代码了
注意，我们需要把$f[0][0]$赋值成1，因为考虑0只羊选0只，总能力对F求余依然是0,也算是F的倍数，所以也是一种方案
但是在题目中要求必须选一只羊，所以我们必须在最后输出答案的时候把这个方案踢出去
最后求出来以后对$10^8$ 求余就好了（要考虑总方案数-1后可能为负，记得加上一个$10^8$再求余哦
AC代码（空间压缩版）：

#include <cstring>
#include <iostream>
using namespace std;
const int M = 1e3 + 1, MOD = 1e8;
int f[M], g[M] /* 这个数组用来辅助空间压缩 */;int main() {int n, F;cin >> n >> F;f[0] = 1;while (n--) {int r;cin >> r;memcpy(g, f, sizeof(int) * F);for (int j = F - 1; j >= 0; j--) {f[j] = (g[j] + g[(j - r + F) % F]) % MOD;}}cout << (f[0] - 1 + MOD) % MOD;return 0;
}