# P2946 [USACO09MAR]牛飞盘队Cow Frisbee Team

## 题目描述

After Farmer Don took up Frisbee, Farmer John wanted to join in the fun. He wants to form a Frisbee team from his N cows (1 <= N <= 2,000) conveniently numbered 1..N. The cows have been practicing flipping the discs around, and each cow i has a rating R_i (1 <= R_i <= 100,000) denoting her skill playing Frisbee. FJ can form a team by choosing one or more of his cows.

However, because FJ needs to be very selective when forming Frisbee teams, he has added an additional constraint. Since his favorite number is F (1 <= F <= 1,000), he will only accept a team if the sum of the ratings of each cow in the team is exactly divisible by F.

Help FJ find out how many different teams he can choose. Since this number can be very large, output the answer modulo 100,000,000.

Note: about 50% of the test data will have N <= 19.

## 输入输出格式

• Line 1: Two space-separated integers: N and F
• Lines 2..N+1: Line i+1 contains a single integer: R_i

• Line 1: A single integer representing the number of teams FJ can choose, modulo 100,000,000.

```4 5
1
2
8
2 ```

`3 `

## 说明

FJ has four cows whose ratings are 1, 2, 8, and 2. He will only accept a team whose rating sum is a multiple of 5.

FJ can pair the 8 and either of the 2's (8 + 2 = 10), or he can use both 2's and the 1 (2 + 2 + 1 = 5).

dp[i][j]表示前i个数，价值和%f为j的方案数

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #define lli long long int
7 using namespace std;
8 const int MAXN=2001;
9 const int maxn=0x7fffffff;
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')
15     x=(x<<1)+(x<<3)+c-48,c=getchar();
16     flag==1?n=-x:n=x;
17 }
18 int n,f;
19 int a[MAXN];
20 int dp[MAXN][MAXN];
21 int tot=0;
22 int  main()
23 {
25     int mod=1e8;
26     for(int i=1;i<=n;i++)
28     dp[0][0]=1;
29     for(int i=1;i<=n;i++)
30     {
31         for(int j=0;j<=f;j++)
32         {
33             dp[i][j]+=dp[i-1][j];
34         //    if(((j-a[i])%f))
35             dp[i][j]+=dp[i-1][(j+a[i])%f];
36             dp[i][j]%=mod;
37         }
38     }
39     cout<<dp[n][f]%mod;
40     return 0;
41 }```

1811 篇文章121 人订阅

0 条评论