[洛谷 2946][USACO09MAR]牛飞盘队

题目链接

https://www.luogu.org/problem/P2946

题解

一道很简单的背包问题。

用 \(f_{i,j}\) 代表选到第 \(i\) 头奶牛，\( \bmod F\) 之后余数为 \(j\) 的方案数。

那么，我们有两种决策：选当前的奶牛和不选。

#include <stdio.h>
#define MOD 100000000
int f[2005][1005],a[2005];
int main()
{
 int n,F;
 scanf("%d%d",&n,&F);
 for(int i=1;i<=n;i++)
 {
  scanf("%d",&a[i]);
  f[i][a[i]%F]=1;
 }
 for(int i=1;i<=n;i++)
  for(int j=0;j<F;j++)
   f[i][j]+=(f[i-1][j]+f[i-1][((j-a[i])%F+F)%F])%MOD,f[i][j]%=MOD;
 printf("%d",f[n][0]);
 return 0;
}