P2946 [USACO09MAR] Cow Frisbee Team S

题目描述

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $N$ 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 $i$ 头奶牛的能力为 $R_i$。飞盘队的队员数量不能少于 $1$、大于 $N$。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 $F$，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 ${10}^8$ 取模的值。

输入格式

第一行：两个用空格分开的整数：$N$ 和 $F$。

第二行到 $N+1$ 行：第 $i+1$ 行有一个整数 $R_i$，表示第 $i$ 头奶牛的能力。

输出格式

第一行：单个整数，表示方案数对 ${10}^8$ 取模的值。

提示

对于 $100\mathrm{\%}$ 的数据，$1\le N\le 2000$，$1\le F\le 1000$，$1\le R_i\le {10}^5$。

思路

01背包的变形,既然如此,先找出状态转移方程组

首先能想到,如果有两种不重叠的组队方式,那么他们结合起来也是符合条件的 于是可以想到,对于第n只奶牛,它能组成的种数取决于前n-1之奶牛中,互补的个数.

于是思路就有了,对每种状态,建立一个数组维护所有的0,1,2...F-1的队伍组合数量,状态转移方程组为:

dp[i][F] = dp[i-1][F-R[i]] + dp[i-1][F]

这时可以发现,F就相当于背包容量了,正常dp就可以了

题解

#include <iostream>

#define MOD 100000000
using namespace std;

long long dp[2048][1024];
long long R[2048];
int N, F;

int main()
{
    // cout << (-3 )% 5 << endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> F;
    for (int i = 1; i <= N; i++)
    {
        cin >> R[i];
        R[i] = R[i] % F;
    }
    R[0] = 0;

    for (int j = 0; j < F; j++)
    {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= N; i++)
    {

        for (int j = 0; j < F; j++)
        // for (int j = F; j < 2 * F; j--)
        {
            // cout << "j - R[i] + F) % F" << (j - R[i] + F) % F << " ";

            dp[i][j] = (dp[i - 1][(j - R[i] + F) % F] + dp[i - 1][j]) % MOD;
        }
        dp[i][R[i]] += 1;
        // for(int p = 0; p < F; p++)
        // {
        //     cout << dp[i][p] << " ";
        // }
        // cout << "\n";
    }
    cout << dp[N][0];
    return 0;
}