【题解】洛谷P2946 [USACO09MAR]Cow Frisbee Team S

这题乍一看是一个朴素的01背包问题，将所有方案的集合按照能力值的和来划分成1~m，然后把m当作体积，把n当作物品数，做一个01背包的代码。于是我兴冲冲地写了代码交上去，然后十组样例只过了八组，另外两个一个MLE, 一个TLE。然后仔细一看数据范围，才发现能力值的和太大了，按照能力值的和来划分子集肯定不行。

所以需要换成另外一种划分方式：按照所有奶牛能力值的和对F取余来划分，划分成0~F-1个集合，于是问题就转化成对这些集合作01背包了。

需要注意的是：

1. 不能用滚动数组优化。因为取余操作，后面的结果会影响到上一层的结果，譬如一个很大的j1和一个很小的j2, j1 更新后，会在j2更新的时候又更新一次（在j1和j2模F同余的时候）。所以只能用二维。

2. j - v[i] % F 有可能出现负数，所以 需要（(j - v[i]) % F + F) % F，这是数学意义上的取余。

状态转移方程为

f[i][j] = f[i][j] + f[i - 1][j] + f[i - 1][((j - v[i]) % F + F)% F]

答案就是模F余0的数，就是f[n][0]。但是由于初始化的时候f[0][0]=1，所以答案需要减一。

代码如下。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2010, mod = 1e8, M = 1010;
typedef long long LL;

int n, F;
int v[N];
int f[N][M];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> F;
    for(int i = 1; i <= n; i++) cin >> v[i];
    
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < F; j++) {
            f[i][j] = LL(f[i - 1][j] + f[i - 1][((j - v[i]) % F + F) % F]) % mod;
        }
    }
    cout << f[n][0] - 1 << endl;
    return 0;
}