[USACO09MAR] Cow Frisbee Team S

题意

有 N 头奶牛，每头奶牛有一个能力值 R_i。

要从这些奶牛里选出一个非空子集，让它们的能力和对 F 取模后等于 0。题目要求输出这样的子集个数，并对 10^8 取模。

这张表把原题翻成了计数 DP：

原题对象	背包/DP 含义
一头奶牛	一个只能选一次的物品
当前和对 `F` 的余数	状态
选择或不选择	转移
满足 `sum % F == 0`	目标状态 `0`

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <bits/stdc++.h>
using namespace std;

const int MOD = 100000000;

int n, f;
vector<int> a;
vector<int> choose_cow; // choose_cow[i] = 0/1，表示第 i 头牛不选/选
int answer = 0;

// 计算当前完整选择序列的总和模 F。
int calc_mod() {
    int sum_mod = 0;
    for (int i = 0; i < n; i++) {
        if (choose_cow[i] == 1) {
            sum_mod = (sum_mod + a[i]) % f;
        }
    }
    return sum_mod;
}

bool check() {
    bool chosen = false;
    for (int i = 0; i < n; i++) {
        if (choose_cow[i] == 1) {
            chosen = true;
        }
    }
    return chosen && calc_mod() == 0;
}

// dfs_choose 只负责枚举完整 01 序列，合法性放到叶子节点统一检查。
void dfs_choose(int dep) {
    if (dep == n) {
        if (check()) {
            answer++;
            if (answer >= MOD) {
                answer -= MOD;
            }
        }
        return;
    }

    // 第 dep 头牛的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_cow[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> f;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    choose_cow.assign(n, 0);
    dfs_choose(0);
    cout << answer % MOD << '\n';

    return 0;
}

brute.cpp 把每头牛看成一个 01 选择：choose_cow[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再统计总和能被 F 整除的非空子集。

这个做法正确，但复杂度是 $O(2^N)$ ，只适合小数据验证。

关键观察是：我们不需要关心当前子集的具体内容，只需要关心它的总和对 F 的余数。

于是设：

dp[r] 表示当前已经考虑若干头牛后，和对 F 取模为 r 的方案数

这张表说明状态定义：

状态	含义
`dp[r]`	当前子集和对 `F` 取模为 `r` 的方案数

初始时：

dp[0] = 1

这表示空集的余数是 0。

处理一头能力值为 x 的牛时：

不选它：余数不变
选它：余数从 r 变成 (r + x) % F

因为每头牛只能选一次，所以要用上一轮的状态转移到下一轮状态。实现时可以把旧数组拷贝到新数组里，再把“选这头牛一次”的贡献加进去。

最后 dp[0] 里包含了空集，所以答案要减去 1。

DP 公式

设 $dp_r$ 表示当前已经考虑若干头牛后，子集和对 $F$ 取模为 $r$ 的方案数。初始化：

dp_0=1

处理一头评分为 $a_i$ 的牛时，如果原余数为 $r$ ，选它后的新余数为：

r'=(r+a_i)\bmod F

转移为：

next_{r'}\leftarrow next_{r'}+dp_r

最终 $dp_0$ 包含空集，所以答案为：

dp_0-1

公式解释：状态只保留当前子集和模 F 的余数。选择一头牛会把余数从 r 推到 (r+a_i) mod F；最后余数为 0 的方案里包含空集，需要减一。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#include <bits/stdc++.h>
using namespace std;

const int MOD = 100000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, f;
    cin >> n >> f;

    // dp[r] 表示当前已经选了若干头牛后，余数为 r 的方案数。
    vector<int> dp(f, 0), ndp(f, 0);
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        // 先拷贝“不选这头牛”的结果，再把“选这头牛一次”加进去。
        ndp = dp;
        int add = x % f;
        for (int r = 0; r < f; r++) {
            int nr = r + add;
            if (nr >= f) {
                nr -= f;
            }
            ndp[nr] += dp[r];
            if (ndp[nr] >= MOD) {
                ndp[nr] -= MOD;
            }
        }

        dp.swap(ndp);
    }

    // dp[0] 包含空集，题目要求非空子集，所以要减去 1。
    cout << (dp[0] + MOD - 1) % MOD << '\n';

    return 0;
}

复杂度

时间复杂度： $O(NF)$
空间复杂度： $O(F)$

总结

这题本质上是一个“按余数做计数 DP”的问题：

只关心和对 F 的余数
每头牛只处理一次
最后从 dp[0] 里去掉空集

以后看到“选一些数，判断和能否被某个数整除，且每个元素最多选一次”这类题，就可以先想余数 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。