这是也是一道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;
}