P2946 [USACO09MAR]牛飞盘队Cow Frisbee Team
2018-06-17 22:12:06来源:未知 阅读 ()
题目描述
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.
农夫顿因开始玩飞盘之后,约翰也打算让奶牛们享受飞盘的乐趣.他要组建一只奶牛飞盘
队.他的N(1≤N≤2000)只奶牛,每只部有一个飞盘水准指数Ri(1≤Ri≤100000).约翰要选出1只或多于1只奶牛来参加他的飞盘队.由于约翰的幸运数字是F(1≤F≤1000),他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数.
帮约翰算算一共有多少种组队方式.
输入输出格式
输入格式:
-
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; 10 void read(int &n) 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 { 24 read(n);read(f); 25 int mod=1e8; 26 for(int i=1;i<=n;i++) 27 read(a[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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷 P2947 [USACO09MAR]向右看齐Look Up 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash