首页 > 其他分享 >P2946 [USACO09MAR]Cow Frisbee Team S

P2946 [USACO09MAR]Cow Frisbee Team S

时间:2023-03-05 19:55:06浏览次数:33  
标签:Frisbee Cow P2946 USACO09MAR int Team

从序列A中选出一些数,使得总和为m的倍数,求有几种选法?

 

 f[i][j] ,考虑前i个,总和的余数为j 时的 方案数 (a[i]%m)

 f[i] [j ]+= f[i-1][j] +f[i-1][ j-a[i] ]

 

#include <bits/stdc++.h>
using namespace std ;
 const int N=2002,mod=1e8;
 int n,m,a[N],f[N][N];
 
 signed main(){
 	int i,j,H,t=0;
 	 cin>>n>>H;
 	 for(i=1;i<=n;i++) cin>>a[i],a[i]%=H;
 	 for(i=1;i<=n;i++) f[i][a[i]]=1;
 	 
 	  for(i=1;i<=n;i++)
 	   for(j=0;j<H;j++){
 	   	 f[i][j]+=f[i-1][j]+f[i-1][(j-a[i]+H)%H];
 	   	 f[i][j]%=mod;
 	   }
 	 cout<<f[n][0];
 }
 
 
 

 

标签:Frisbee,Cow,P2946,USACO09MAR,int,Team
From: https://www.cnblogs.com/towboa/p/17181436.html

相关文章

  • 【题解】洛谷P2946 [USACO09MAR]Cow Frisbee Team S
    这题乍一看是一个朴素的01背包问题,将所有方案的集合按照能力值的和来划分成1~m,然后把m当作体积,把n当作物品数,做一个01背包的代码。于是我兴冲冲地写了代码交上去,然后十组样......